力扣解题思路：分割数组/背包问题（动态规划）纠错记录

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

显然这就是一个0-1背包问题背包问题的讲解可以参考这里o(￣▽￣)ブ首先我们的目的是确定背包的容量，也就是sum / 2，而且不多不少刚好sum / 2，当然sum也必须是个偶数，否则返回false，每个物品也就是数组里的每个元素，可以放也可以不放，那么我们用二位动态规划数组来记录更新过程，dp[m][n] 考虑是否将第m个数字放入容量为n的背包，那么状态转移方程：
dp[m][n] = dp[m-1][n] || dp[m-1][n-nums[m]]
当然我们还需要对数组进行初始化（这里写一个循环是为了避免nums[0]比c大的这种情况，但测试用例中似乎没有出现这种情况）：

for(int i=0; i<=c; i++){
    if(i!=nums[0]){
        dp[0][i] = false;
    }else{
        dp[0][i] = true;
    }
}

当然初始化也可以这样：

        dp[0][0] = true;       
        dp[0][nums[0]] = true;

因为i=0时只有这两种可能，就是放一个nums[0]刚好满了，或者不放nums[0]（什么都不妨）也能刚好满（因为背包大小为0）。完整代码如下：

public boolean canPartition(int[] nums) {
    //动态规划，背包问题，从nums中选择一部分数字组合，填满容量为sum/2的背包 
    int n=nums.length;
    if(n == 0){
        return false;
    }
    int sum = 0;
    for(int i=0; i<n; i++){
        sum+=nums[i];
    }
    int c = sum/2; 
    if(sum%2==1){
        return false;
    }
    boolean[][] dp = new  boolean[n][c+1];
    //状态初始化
    for(int i=0; i<=c; i++){
        if(i!=nums[0]){
            dp[0][i] = false;
        }else{
            dp[0][i] = true;
        }
    }
    //状态转移方程：dp[m][n] = dp[m-1][n] || dp[m-1][n-nums[m]]
    for(int i=1; i<n; i++){
        for(int j=0; j<=c; j++){
            if(nums[i]<=j){
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];                    
            }else{
                dp[i][j] = dp[i-1][j];
            }
            
        }
    }
    return dp[n-1][c];       
}

另外我再解释一下为什么这里的数组长度为c+1而不是c，这是因为在遍历时要考虑背包中只剩0或者只剩c的情况，如果数组长度为c则数组下标最大值为c-1而不是c，所以这是不对的。
接下来进行空间优化，由dp[m][n] = dp[m-1][n] || dp[m-1][n-nums[m]]可知m-1就是上一个循环中的m,所以动态规划数组的第一个维度可以去掉，那么更新动态规划数组的更新方式可以改为：

for(int num:nums){
    for(int j=0;j<=W;j++){
        if(num<=j){
                dp[j] = dp[j] || dp[j-num];                    
            }else{
                dp[j] = dp[j];
            }
    }
}

然而这个答案并不对，这里错误原因就是当我们把dp矩阵压缩到一维时我们采用的正向更新，而正确的应该是采用逆向更新。因为dp[j] = dp[j] || dp[j - nums[i]] 可以理解为 dp[j] （新）= dp[j] （旧） || dp[j - nums[i]] （旧），如果采用正序的话 dp[j - nums[i]]会被之前的操作更新为新值。（为什么不可以用新值呢？首先这一题是0-1背包问题，而不是完全背包问题，也就是说每个元素只能使用一次，如果是完全背包问题则每个元素可以使用多次，如518. 零钱兑换 II，也可以通过画表看出，如果采用完全背包的方式，那么所有的格子里都是true，显然不符合题意！！！）

当时我还思考了，如果采用了逆序dp[j]需要用到之前的dp[j - nums[i]] 该怎么办，后来我发现dp[j]是依赖于上一轮的dp[j - nums[i]] ，所以第二层循环的顺序并不会影响结果，只不过因为我们用的一维数组所以会产生覆盖结果的情况，所以只能逆序，而我刚才的错误想法正是受了那些一维动态规划数组更新规则（没有状态压缩，一层循环，不会用到上一层的旧值）的影响，而这一题本身就是二维动态规划，只不过时进行了状态压缩（因为是有两层循环的）。

for (int num : nums) {                 // 0-1 背包一个物品只能用一次
    for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
        dp[i] = dp[i] || dp[i - num];
    }
}

防止将 dp[i-1][j-num] 覆盖，需要先计算 dp[i][j] 再计算 dp[i][j-num]，s所以在程序实现时需要按倒序来循环求解。另外，在初始化的时候只需要初始dp[0] = true即可，这样写也可以：

for(int num:nums){
    for(int j=W;j>=0;j--){
        if(num<=j){
                dp[j] = dp[j] || dp[j-num];                    
            }else{
                dp[j] = dp[j];
            }
    }
}

完整代码如下：

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    int W = sum / 2;
    boolean[] dp = new boolean[W + 1];
    dp[0] = true;
    for (int num : nums) {                 // 0-1 背包一个物品只能用一次
        for (int i = W; i >= num; i--) {   // 从后往前，先计算 dp[i] 再计算 dp[i-num]
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[W];
}

注意，初始化的时候不需要初始化dp[nums[0]] = true（会导致结果错误），因为我们对数组时从nums[0]开始遍历的而不是像上一种解法一样从nums[1]开始的（如果遍历时从nums[1]开始的也可以初始化dp[nums[0]] = true啦o(￣▽￣)o）。
还有一个类似的：

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

这一题最直观的方法就是DFS也是最简单的方法，代码比较简单就直接给出了：

int count = 0;
public int findTargetSumWays(int[] nums, int S) {
    int len = nums.length;
    dfs(nums,S,0,len);
    return count;
}
public void dfs(int[] nums,int s,int i,int len){
    if(i==len&&s==0){
        count++;
        return;
    }
    if(i==len){
        return;
    }
    int s1 = s - nums[i];
    int s2 = s + nums[i];
    dfs(nums,s1,i+1,len);
    dfs(nums,s2,i+1,len);
}

接下来讨论动态规划方法，可以将这组数看成两部分，P 和 N，其中 P 使用正号，N 使用负号，有以下推导：

sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

因此只要找到一个子集，令它们都取正号，并且和等于 (target + sum(nums))/2，就证明存在解。

这仍然是一个背包问题，可以采用二维动态数组：

public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    for(int i=0;i<nums.length;i++) sum += nums[i];
    if((S + sum)%2 == 1 || sum < S) return 0;
    int w = (S + sum)/2;
    int[][] dp = new int[nums.length+1][w+1];
    dp[0][0] = 1;
    //if(w >= nums[0]) dp[0][nums[0]] = 1;
    for(int i=1;i<=nums.length;i++){
        for(int j=0;j<=w;j++){//不可以写成j=nums[i-1]!!!因为小的j也需要被更新
            if(nums[i-1]<=j){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[nums.length][w];
}

注意最好这里把动态规划数组长度都设置多1，这样可以避免很多边界问题，最开始就是我设置成了int[nums.length][w+1]导致各种边界问题，这里测试用例中是很多S为0，或者数组元素为0的这种情况，所以w也不可以从1开始更新！！
但是要注意内层循环一定要从0开始！！

当动态数组设置为int[nums.length][w+1]我尝试了各种初始化的方法都没有成功。。。等我想出正确的方法再更新吧。。。

我们可以根据上面的二维动态规划改写成一维动态规划，更新方式为dp[i] = dp[i] + dp[i - num]，这里注意内层循环一定要倒着更新噢~因为每个元素只能使用一次！！这里注意区分普通背包和完全背包问题！！

完整代码如下：

public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum < S || (sum + S) % 2 == 1) {
        return 0;
    }
    int W = (sum + S) / 2;
    int[] dp = new int[W + 1];
    dp[0] = 1;
    for (int num : nums) {
        for (int i = W; i >= num; i--) {
            dp[i] = dp[i] + dp[i - num];
        }
    }
    return dp[W];
}

再看一个完全背包问题：

思路：
首先这是个完全背包问题，普通的一维数组可以解决，且内层循环无需逆序：

public int change(int amount, int[] coins) {
    int dp[] = new int[amount+1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int j = 1; j <= amount; j++) {
            if (j >= coin) {
                dp[j] = dp[j] + dp[j - coin];
            }
        }
    }
    return dp[amount];
}

然后我想写全两种方法，所以又写了个二维的动态规划：

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];
    dp[0][0] = 1;
    for(int i=1;i<=coins.length;i++){
        for(int j=0;j<=amount;j++){//一定要从0开始！！！
            if(j>=coins[i-1]){
                dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]];
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[coins.length][amount];
}

注意内层循环一定要从0开始，但是居然还是错了！问题就在于

dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]];

这句，因为完全背包问题物品可以重复使用，所以这里用dp[i][j-coins[i-1]]（当前层）而不是dp[i-1][j-coins[i-1]]（上一层），所以我在这里再次强调一遍要分清楚完全背包和普通背包！！

所以正确代码如下：

public int change(int amount, int[] coins) {
    int[][] dp = new int[coins.length+1][amount+1];
    dp[0][0] = 1;
    for(int i=1;i<=coins.length;i++){
        for(int j=0;j<=amount;j++){
            if(j>=coins[i-1]){
                dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];//完全背包问题物品可以重复使用，所以这里用dp[i][j-coins[i-1]]（当前层）而不是dp[i-1][j-coins[i-1]]（上一层）
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[coins.length][amount];
}

思路：
类似上面思路，由于我们要求的是最小值，所以数组中的元素要初始化为最大值：

public int coinChange(int[] coins, int amount) {//二维
    int[][] dp = new int[coins.length][amount+1];
    for(int[] d : dp) Arrays.fill(d,Integer.MAX_VALUE);
    dp[0][0] = 0;
    //dp[0][coins[0]] = 1;
    for(int i=1;i<amount+1;i++){
        if(i%coins[0] == 0){
            dp[0][i] = i/coins[0];
        }
    }
    for(int i=1;i<coins.length;i++){
        for(int j=0;j<amount+1;j++){
            if(j>=coins[i] && dp[i][j - coins[i]] != Integer.MAX_VALUE){
                dp[i][j] = Math.min(dp[i][j-coins[i]]+1,dp[i-1][j]);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[coins.length-1][amount] == Integer.MAX_VALUE? -1:dp[coins.length-1][amount];
}

有几点需要注意的：

1. dp[i][j] = Math.min(dp[i][j-coins[i]]+1,dp[i-1][j])中不可以写成 dp[i-1][j-coins[i]]，原因和上一题一样，因为所有物品可以重复使用，是完全背包问题！！
2. 注意初始化，因为我们在两层循环中是从i=1开始遍历的，并且声明的dp数组的行数为coins.length，所以dp数组的第一行需要我们提前初始化。

如果不想这么复杂的初始化，也可以将数组行数多加一行：

    public int coinChange(int[] coins, int amount) {//二维
        int[][] dp = new int[coins.length+1][amount+1];
        for(int[] d : dp) Arrays.fill(d,Integer.MAX_VALUE);
        dp[0][0] = 0;
        //dp[1][coins[0]] = 1;
        // for(int i=1;i<amount+1;i++){
        //     if(i%coins[0] == 0){
        //         dp[0][i] = i/coins[0];
        //     }
        // }
        for(int i=1;i<=coins.length;i++){
            for(int j=0;j<=amount;j++){
                if(j>=coins[i-1] && dp[i][j - coins[i-1]] != Integer.MAX_VALUE){
                    dp[i][j] = Math.min(dp[i][j-coins[i-1]]+1,dp[i-1][j]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[coins.length][amount] == Integer.MAX_VALUE? -1:dp[coins.length][amount];
    }

3. 除了初始化的数据外，因为我们所求是最少硬币数，所以需要将其他数设置为最大值。那么这就会出现一个问题，如果dp[i][j - coins[i]] == Integer.MAX_VALUE 则 dp[i][j-coins[i]]+1 会溢出，导致 dp[i][j-coins[i]]+1 才是最小值，这样显然是错的！！所以我们将 j>=coins[i] 判断写成 j>=coins[i] && dp[i][j - coins[i]] != Integer.MAX_VALUE 就可以啦~~

我们还可以进行空间优化写成一维数组，去掉第一维就可以啦：

int[] dp = new int[amount+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i=0;i<coins.length;i++){
    for(int j=0;j<amount+1;j++){
        if(j-coins[i] >= 0 && dp[j-coins[i]] != Integer.MAX_VALUE){
            dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
        }
    }
}
return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
}

n = 2
return 1 (2 = 1 + 1)

n = 10
return 36 (10 = 3 + 3 + 4)

可以使用贪心算法，也可以使用动态规划，这里使用动态规划更简单，不用考虑太多的。每一个数都可以拆分成i + j的模式，其中i, j分别可选拆或这不拆，取其中可贡献的最大值即可：

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
    return dp[n];
}

其中j * (i - j)表示不拆，dp[j] * (i - j)表示拆，当然也可以换种写法，初始化的时候都初始化成不拆的乘积，然后后续只需于dp[j] * (i - j)比较即可：

public int integerBreak(int n) {
    int[] dp = new int[n+1];
    for(int i=0;i<n;i++) dp[i] = i;
    for(int i=2;i<n+1;i++){
        for(int j=1;j<i;j++){
            dp[i] = Math.max(dp[i],dp[i-j]*j);
        }  
    }
    return dp[n];
}

贪心算法（参考这里~~）：

尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。

public int integerBreak(int n) {
    if (n < 2)
        return 0;
    if (n == 2)
        return 1;
    if (n == 3)
        return 2;
    int timesOf3 = n / 3;
    if (n - timesOf3 * 3 == 1)
        timesOf3--;
    int timesOf2 = (n - timesOf3 * 3) / 2;
    return (int) (Math.pow(3, timesOf3)) * (int) (Math.pow(2, timesOf2));
}

还有杨辉三角这题也是需要倒着更新的：