LeetCode 465最优账户平衡问题解法解析及疑问咨询

给定交易数组transactions，其中transactions[i] = [fromi, toi, amounti]表示ID为fromi的人向ID为toi的人转账amounti美元，返回结清所有债务所需的最少交易次数。

示例 #

示例1 #

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

示例2 #

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

约束条件 #

1 <= transactions.length <= 8
transactions[i].length == 3
0 <= fromi, toi < 12
fromi != toi
1 <= amounti <= 100

我的疑问 #

• 我正尝试理解以下DP代码中的DP函数工作机制，我对位运算（位移、异或、mask）有模糊认知，但无法将它们在该示例中结合起来理解。
• 希望您讲解该DP函数的记忆化存储内容、时间复杂度，以及其优化优势。
• 我自己实现了回溯解法，直觉认为其时间复杂度为O(n²)（n为balance数组长度），请帮忙验证该结论是否正确。

参考代码 #

DP解法代码 #

class Solution:
    def minTransfers(self, T: List[List[int]]) -> int:
        p = [0] * 12
        for f,t,a in T:
            p[f] -= a
            p[t] += a
        arr = []
        for a in p:
            if a != 0:
                arr.append(a)
        memo = {}
        def dp(count, cur, mask):
            nonlocal memo
            if (count, cur, mask) in memo:
                return memo[(count, cur, mask)]
            if mask == 0:
                return 0
            res = inf
            for i in range(len(arr)):
                if (1<<i)&mask:
                    if cur+arr[i]==0:
                        res = min(res, dp(0, 0, (1<<i)^mask)+count)
                    else:
                        res = min(res, dp(count+1, cur+arr[i], (1<<i)^mask))
            memo[(count, cur, mask)] = res
            return res
        mask = (1<<len(arr))-1
        return dp(0,0,mask)

我的回溯解法代码 #

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        # hash person giving and receiving money 

        map = {}

        for i in transactions:
            map[i[0]] = map.get(i[0],0)-i[2]
            map[i[1]] = map.get(i[1],0)+i[2]
        
        balance = [] 
        for key,val in map.items():
            if val != 0:
                balance.append(val)
        
        def backtrack(idx):
            if idx == len(balance):
                return 0 
            
            if balance[idx] == 0:
                return backtrack(idx+1)
            
            result = float('inf')

            for curr in range(idx+1,len(balance)):
                
                if balance[idx]*balance[curr] < 0:
                    balance[curr]+= balance[idx]
                    result = min(result,1+backtrack(idx+1))
                    balance[curr]-= balance[idx]
            return result 
        
        return backtrack(0)

内容的提问来源于stack exchange，提问作者Kang_the_Conqueror