动态规划——最后一块石头的重量（python）

思路两两石头之间可以相互抵消所以将所有石头加起来除以2得到目标值target背包容量接下来就是尽可能凑出这个最大的容量求最大值。dp[i]定义为凑成最大重量i的最大重量为dp[i]。因为是求最大所以dp数组初始化为全0,使用max()。状态转移方程为dp[i]max(dp[i],dp[i-stones[i]]stones[i])#最后一块石头的重量 def lastStone(stones): totalsum(stones) targettotal//2 dp[0]*(target1) for i in range(len(stones)): for j in range(target,stones[i]-1,-1): dp[j]max(dp[j],dp[j-stones[i]]stones[i]) return total-dp[target]*2 def main(): stoneslist(map(int,input().split())) reslastStone(stones) print(res) if __name____main__: main()