Leetcode 465. 最优账单平衡

1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/optimal-account-balancing/description/

2.解题方法

2.1.解题思路

子集状态压缩动态规划(子集状压dp)，使用二进制整数来表示数组cnts中的子集的动态规划

2.2.解题步骤

第一步，构建各个交易的cnts数组，以及进行状态定义。

• 1.1.构建cnts数组，cnts总共12个位置（因为交易总数最多12个），cnts[i]表示交易人的待进账（也就是借出去的总额）

• 1.2.状态定义。dp[i]表示子集i的最小交易次数，这里使用二进制数字i中各个位上为1的状态确定cnts中的子集（也就是状态压缩），对于长度为n的数组，也刚好有2^n个子集。

第二步，状态初始化。dp[0]=0，表示空子集的转换次数为0；这在初始化时已经完成。

第三步，状态转移。如果i子集的和不为0，则不可能转换完成，那么dp[i]=inf；如果i子集的和为0，则枚举i的子集j，dp[i]=min([dp[j]+dp[i^j] for j in i的子集])（其中i^j为i中j子集的补集）（i的子集通过k=(i-1)&i，k=(k-1)&i进行枚举）

• 3.1.计算子集i的和

• 3.2.子集和不为0，则不可能通过有限的交易使其全部为0，此时dp[i]=inf

• 3.3.子集和为0，则枚举i子集的子集j，进行状态转移，每次j更新都获取距离当前子集最近的i的子集（这是枚举子集的模板方法，记下来）

第四步，m-1子集即所有12个人都参与进行交换，哪些不存在的人的cnts为0。所以dp[m-1]即为题解

3.解题代码

python代码

class Solution:def minTransfers(self, transactions: List[List[int]]) -> int:# 思路：子集状态压缩动态规划(子集状压dp)，使用二进制整数来表示数组cnts中的子集的动态规划# 第一步，构建各个交易的cnts数组，以及进行状态定义。# 1.1.构建cnts数组，cnts总共12个位置（因为交易总数最多12个），cnts[i]表示交易人的待进账（也就是借出去的总额）n = 12m = 1 << ncnts = [0] * nfor f, t, amount in transactions:cnts[f] += amountcnts[t] -= amount# 1.2.状态定义。dp[i]表示子集i的最小交易次数，这里使用二进制数字i中各个位上为1的状态确定cnts中的子集（也就是状态压缩），对于长度为n的数组，也刚好有2^n个子集。dp = [0] * m# 第二步，状态初始化。dp[0]=0，表示空子集的转换次数为0；这在初始化时已经完成。# 第三步，状态转移。如果i子集的和不为0，则不可能转换完成，那么dp[i]=inf；如果i子集的和为0，则枚举i的子集j，dp[i]=min([dp[j]+dp[i^j] for j in i的子集])（其中i^j为i中j子集的补集）（i的子集通过k=(i-1)&i，k=(k-1)&i进行枚举）for i in range(m):# 3.1.计算子集i的和sum_ = 0for j in range(n):if (i >> j) & 1:    # i子集的二进制第i位上是1sum_ += cnts[j]if sum_ != 0:# 3.2.子集和不为0，则不可能通过有限的交易使其全部为0，此时dp[i]=infdp[i] = infelse:# 3.3.子集和为0，则枚举i子集的子集j，进行状态转移，每次j更新都获取距离当前子集最近的i的子集（这是枚举子集的模板方法，记下来）dp[i] = bin(i).count('1') - 1j = (i - 1) & iwhile j > 0:dp[i] = min(dp[i], dp[j] + dp[i ^ j])j = (j - 1) & i# print(dp)# 第三步，m-1子集即所有12个人都参与进行交换，哪些不存在的人的cnts为0。所以dp[m-1]即为题解return dp[m - 1]

4.执行结果