外贸网站建设哪家实惠_小型网站搭建_信息互联网推广_南宁seo优化公司排名

1049最后一块石头的重量

这道题和昨天的分割等和子集的类型很像，只需要想到求最小的石头的重量可以转化为将原数组分割为两个元素总和大小尽量相同的数组，然后求dp[target]的大小即可。target表示原数组总和sum的一半，dp[target]表示石头的总价值。

494目标和

这道题比较难理解，思路也很巧妙。首先因为每个数都有取和不取两种状态，所以这题可能可以用动态规划来解决。然后一个比较巧妙的思路是将整个数组划分为两个部分，一个部分全部取正号，另一个部分全部取负号，这样目标和只需将正数部分减去负数部分。所以可以列出方程：

positive+negative=sum,positive-negative=target，解得negative=(sum-target)/2,同时如果(sum-target)为奇数，说明不可能有满足题意的添加符号的方式。接着设立dp数组，二维dp数组dp[i][j]表示在前i个数中总和为j的情况有dp[i][j]种，所以dp[0][0]表示在前0个数中总和为0的情况，所以dp[0][0]=0.再考虑递推公式，当j<num[i]时，dp[i][j]=dp[i-1][j];，当j>num[i]时，有取和不取num[i]的情况，因此dp[i][j]=dp[i-1][j]+dp[i-1][j-num[i]],这里取num[i]表示的时先空出物品i的容量，然后用前i-1个元素装满背包。

474一和零

这题令人眼前一亮的做法是原来可以使用三维dp数组，然后用dp[i][j][k]中j表示0的数量，k表示1的数量，其它部分就和01背包一样了。