416. 分割等和子集 新思路
定义
dp[j]表示背包总容量是j,放进物品后,背包是否装满
递推公式
dp[j] = dp[j - nums[i]] || dp[j];
dp[j]是否装满取决于情况一或者情况二:
情况一:放入物品i,是否装满,即判断dp[j - nums[i]]是否已经满了
情况二:不放入物品i,是否装满,即判断dp[j]是否装满
初始化
dp[0] = true;
其余为false
当j==nums[i]时,dp[j - nums[i]]一定为装满
其余按照定义应该为未装满
遍历顺序
先物品,后倒序遍历背包
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/d4fd9223164a46509ff006ebd3a83321.png)
总结
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/b4b8398ef8de4942aab4df22036ebf4b.png)
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/ca831408cc88469caccd97768a622939.png)