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分钟
