代码随想录算法训练营19期第43天

 1049. 最后一块石头的重量 II  

视频讲解：动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录  

初步思路：动态规划。

总结：套用01背包

dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

先遍历物品嵌套遍历背包容量(背包是从大到小)

用时：45分钟

494. 目标和 

视频讲解：动态规划之背包问题，装满背包有多少种方法？| LeetCode：494.目标和_哔哩哔哩_bilibili

代码随想录  

初步思路：动态规划。

总结：

假设加法的总和为x，那么减法对应的总和就是sum – x -> 装满容量为x的背包，有几种方法

dp[j] 表示 填满j（包括j）这么大容积的包，有dp[j]种方法

dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法

1D递推公式dp[j] += dp[j - nums[i]]

2D递推公式 dp[i][j]=dp[i−1][j]+dp[i−1][j−nums[i]]

用时：45分钟

 474.一和零  

视频讲解：动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零_哔哩哔哩_bilibili

代码随想录  

初步思路：动态规划。

总结：

m 和 n相当于是一个背包，两个维度的背包.

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]

递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

字符串的zeroNum和oneNum相当于物品的重量，字符串本身的个数相当于物品的价值。

dp[i][j][k] 表示在前i个输入字符串在中， 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。

不选择当前考虑的字符串： dp[i-1][j][k]

选择当前考虑第i个字符串: dp[i−1][j−当前字符串使用0的个数][k−当前字符串使用1的个数]+1

用时：45分钟