一道题求解惑

leetcode 416
我用两种解法都能ac，能写出两种解法完全不是因为融会贯通和举一反三，而是因为看其他的01背包问题的解题方法，这两种都出现过，但其实自己并不能理解为什么两种方法都行。
说实话解法一我倒能理解一点，因为可以根据一个没有mem优化的解法推演出来，解法二就完全弄不明白了

解法一：

1. public class Solution
   
2.     {
   
3.         public bool CanPartition(int[] nums)
   
4.         {
   
5.             var sum = nums.Sum();
   
6.             if (sum % 2 > 0)
   
7.             {
   
8.                 return false;
   
9.             }
   
10. 
    
11.             var target = sum / 2;
    
12.             var dp = new bool[target + 1];
    
13.             dp[0] = true;
    
14.             for (var i = 0; i < nums.Length; ++i)
    
15.             {
    
16.                 for (var j = nums[i]; j <= target; ++j)
    
17.                 {
    
18.                     if (dp[j - nums[i]])
    
19.                     {
    
20.                         dp[j] = true;
    
21.                     }
    
22.                 }
    
23.             }
    
24. 
    
25.             return dp[target];
    
26.         }
    
27.     }

复制代码

解法二：

1. public class Solution
   
2.     {
   
3.         public bool CanPartition(int[] nums)
   
4.         {
   
5.             var sum = nums.Sum();
   
6.             if (sum % 2 > 0)
   
7.             {
   
8.                 return false;
   
9.             }
   
10. 
    
11.             var target = sum / 2;
    
12.             var dp = new bool[target + 1];
    
13.             dp[0] = true;
    
14.             for (var i = nums.Length - 1; i >= 0; --i)
    
15.             {
    
16.                 for (var j = target; j >= nums[i]; --j)
    
17.                 {
    
18.                     dp[j] = dp[j] || dp[j - nums];[i][i]
    
19.                 }
    
20.             }
    
21. 
    
22.             return dp[target];
    
23.         }
    
24.     }

复制代码

[/i][/i][/i][/i]

补充内容 (2021-1-1 19:45):
感谢大神的解答，我解法一copy了一个之前错误的解法，解法二才是正解
第一种是完全背包问题，第二种是01背包问题
另外，还有多重背包问题

luke77gu 发表于 2021-1-1 19:58
第一个是从小到大推dp公式，第二种是从target减小到nums，两种看上去都很合理啊。

还是不一样的
解法一，是完全背包问题，也就是每个物品数量没有限制
解法二，是01背包问题，每个物品最多一个
可以看看这个blog：https://blog.csdn.net/wzy_1988/article/details/12260343

不知道你用的什么语言，有点像Java，但是又不是。第一种写法应该对应的是完全背包问题，这个题目应该是过不了的。第二种写法对应的才是0-1背包问题。

不知道小帅 发表于 2021-01-01 18:47:11
不知道你用的什么语言，有点像Java，但是又不是。第一种写法应该对应的是完全背包问题，这个题目应该是过不了的。第二种写法对应的才是0-1背包问题。

语言是c#，两种都过了

JoyForce 发表于 2021-1-2 11:20
语言是c#，两种都过了

【1， 2， 5】这个情况的话，第一个应该是return true啊，实际应该是false吧

不知道小帅 发表于 2021-1-1 19:27
【1， 2， 5】这个情况的话，第一个应该是return true啊，实际应该是false吧

哦哦，我解法一 copy 错了，又仔细看了一下两种解法是一模一样的。。谢谢解答
01背包和完全背包的解法太相似了，是不是差别只有内层循环的遍历顺序不一样？

JoyForce 发表于 2021-01-01 19:42:47
哦哦，我解法一 copy 错了，又仔细看了一下两种解法是一模一样的。。谢谢解答
01背包和完全背包的解法太相似了，是不是差别只有内层循环的遍历顺序不一样？

是的，01内层循环从大到小，完全背包从小到大。其实是从二维的dp转移方程优化过来的。

第一个是从小到大推dp公式，第二种是从target减小到nums[i]，两种看上去都很合理啊。