0465：最优账单平衡（★★）

力扣第 465 题

题目

给你一个表示交易的数组 transactions ，其中 transactions[i] = [fromi, toi, amounti] 表示 ID = fromi 的人给 ID = toi 的人共计 amounti $ 。

请你计算并返回还清所有债务的最小交易笔数。

示例 1：

输入：transactions = [[0,1,10],[2,0,5]]
输出：2
解释：
#0 给 #1 $10 。
#2 给 #0 $5 。
需要进行两笔交易。一种结清债务的方式是 #1 给 #0 和 #2 各 $5 。

示例 2：

输入：transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
输出：1
解释：
#0 给 #1 $10 。
#1 给 #0 $1 。
#1 给 #2 $5 。
#2 给 #0 $5 。
因此，#1 只需要给 #0 $4 ，所有的债务即可还清。

提示：

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

分析

先计算出每人的总债务，该收钱的即为正，该换钱的即为负

• 假如 k 个人的债务和为 0，那么 k-1 次交易即可将这 k 个清零，节省一次交易
• 因此找到一种划分，使得和为 0 的子集数最多， 即得到最小交易数
• 集合划分容易想到状压 dp，令 dp[st] 表示集合 st 最多能划分的和为 0 的子集数，即可递推
• 还可以提前存储集合 st 的和，优化递推时间

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        ct = defaultdict(int)
        for a,b,w in transactions:
            ct[a] -= w
            ct[b] += w
        A = [a for a in ct.values() if a]
        m = len(A)
        d = defaultdict(int)
        for st in range(1,1<<m):
            x = st.bit_length()-1
            d[st] = d[st^1<<x]+A[x]
        dp = [0]*(1<<m)
        for st in range(1,1<<m):
            dp[st] = (d[st]==0)+max(dp[st^1<<j] for j in range(m) if st&1<<j)
        return m-dp[-1]

60 ms