动态规划：分割等和子集

参考资料：代码随想录

题目链接：. - 力扣（LeetCode）

这道题是01背包问题的抽象，这道题的难点在于怎么绕明白遍历顺序是从后往前。

题目中给的nums数组，以nums=[1,5,11,5]为例，可以分析为有4个物品，每个物品的重量为weight=[1,5,11,5],每个物品的价值为value=[1,5,11,5]

最大容量为：（1+5+11+5）/2

1.确定dp数组含义

重量从0到maxWeight，分别能装的最大价值

2.初始化dp数组

全部初始化为0

3.确定遍历顺序

只能选取一次，从后向前

4.确定递推公式

class Solution {public boolean canPartition(int[] nums) {//求最大重量int sum = 0;for(int num:nums){sum+=num;}if(sum%2 != 0) return false;int maxWeight = sum/2;//1.确定dp数组含义int[] dp = new int[maxWeight+1];//2.初始化dp数组//3.确定遍历顺序for(int i = 0;i < nums.length;i++){for(int j = maxWeight;j >=nums[i] ;j--){//4.确定递推公式if(j >= nums[i]){dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}}return dp[maxWeight] == maxWeight;}
}