LCR 101. 分割等和子集

解题思路

• 背包问题思路：给一个可以装载重量为sum / 2的背包和N个物品 每一个物品的重量为nums[i],现在装物品 能否装满

• 动态规划表格： 使用二维数组 dp，其中 dp[i][j] 表示前 i 个物品能否填满重量为 j 的背包。

• Base Case 初始化： 当背包容量为 0 时，对于任意物品都能满足，因此 dp[i][0] 初始化为 true。

• 状态转移方程： 通过填表的方式计算状态转移。对于每个物品，考虑是否将其装入背包，根据状态转移方程进行更新。状态转移方程如下：

• 如果 j - nums[i - 1] < 0，表示当前物品无法装入背包，继承上一行的状态：dp[i][j] = dp[i - 1][j]。
  否则，当前物品可以选择装入或不装入背包，取决于前一个状态：dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]。

• 结果判断： 最终结果存储在 dp[n][sum]，其中 n 为数组长度，sum 为数组元素之和的一半。如果该值为 true，则说明存在一种分割方式，使得两个子数组的和相等；否则，不能进行等和分割。

class Solution {public boolean canPartition(int[] nums) {// 也就是寻找一个数组 使得元素之和等于nums的所有元素之和的一半// 给一个可以装载重量为sum / 2的背包和N个物品 每一个物品的重量为nums[i],现在装物品 能否装满int sum = 0;for(int num: nums){sum += num;}if(sum% 2 != 0){return false;}int n = nums.length;sum = sum  / 2;boolean[][] dp = new boolean[n + 1][sum + 1];// 计算Base casefor(int  i = 0; i <= n; i++){dp[i][0]= true;// 背包的重量是0  都是true}for(int i = 1; i <=n; i++){for(int j = 1; j <= sum; j++){if(j - nums[i - 1] < 0 ){// 说明该物品不能装进背包dp[i][j] = dp[i - 1][j];}else{// 装进背包 或者不装进背包dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];}}}return dp[n][sum];// 表示从前面所有N个物品 填满sum的背包的方法}
}