416. 分割等和子集

題目鏈接：416. 分割等和子集 - 力扣（LeetCode）

文章講解：代碼隨想錄

視頻講解：動態規劃之背包問題，這個包能裝滿嗎？| LeetCode：416.分割等和子集_嗶哩嗶哩_bilibili

思路：

1. 確定dp數組以及下標的含義

01背包中，dp[j] 表示： 容量（所能裝的重量）為j的背包，所背的物品價值最大可以為dp[j]。

如果背包所載重量為target， dp[target]就是裝滿 背包之后的總價值，本題中每一個元素的數值既是重量，也是價值，當 dp[target] == target 的時候，背包就裝滿了。

2. 確定遞推公式

01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

相當于背包里放入數值，那么物品i的重量是nums[i]，其價值也是nums[i]。

所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

去掉物品i容量的最大價值+物品i的價值就是當前i容量的最大價值

(相當于背包問題二維變一維去掉前面的i，下面是背包問題二維寫法）

不放物品i：背包容量為j，里面不放物品i的最大價值是dp[i - 1][j]。

放物品i：背包空出物品i的容量后，背包容量為j - weight[i]，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]且不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值

遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp數組如何初始化

在01背包，一維dp如何初始化，已經講過，

從dp[j]的定義來看，首先dp[0]一定是0。

4.確定遍歷順序

因為從左上角和正上找數，倒序就不會覆蓋之前的值，因為推導只用到左上和上邊的數據，所以要從最右邊遍歷

5.舉例推導dp數組