LeetCode1049. 最后一块石头的重量 II 这道题难点在于如何转换成背包问题,其实和上一题和相等子集合基本一样,尽量把石头分成两个重量相等的集合,那么在碰撞之后和就是最小的,石头的重量也可以当作石头的价值,代码也基本一样,就是最后的返回值是返回最小的差值,除法是向下取整,所以sum-dp[target]>dp[target]。 代码如下:时间复杂度O(m*n);空间复杂度O(m)。
文章目录 一、题目二、题解 一、题目 You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-’ before each integer in num