代码随想录算法训练营第44天

今日任务

● 完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

链接：https://docs.qq.com/doc/DUHBSRVRUc0Vsck1z (opens in a new tab)

完全背包

使用二维数组

因为是完全背包问题，所以在考虑“放入当前物品”时， 我们仍然可以选择当前物品，所以是dp[i][j-weights[i]]而不是dp[i-1][j-weights[i]]

public int maxProfit(int[] weights, int[] values, int n, int w) {
    int[][] dp = new int[n][w + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j >= weights[i]) {
                if (i == 0) dp[i][j] = dp[i][j - weights[i]] + values[i];  // 这句可以认为是初始化
                else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i]] + values[i]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][w];
}

使用一维数组

与01背包不同的是，

  1. 完全背包问题的内层循环是从小到大遍历的，因为我们可以重复放入当前物品。

  2. 可以先遍历物品，再遍历背包，也可以先遍历背包，再遍历物品。

  3. 遍历顺序的不同，在实际应用中一般对应组合或排序问题。

//先遍历物品，再遍历背包
public int maxProfit(int[] weights, int[] values, int n, int w) {
    int[] dp = new int[w + 1];
    for (int i = 0; i < n; i++) {
        for (int j = weights[i]; j <= w; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[w];
}
 
//先遍历背包，再遍历物品
public int maxProfit(int[] weights, int[] values, int n, int w) {
    int[] dp = new int[w + 1];
    for (int i = 1; i <= w; i++) {
        for (int j = 0; j < n; j++) {
            if (i - weights[j] >= 0){
                dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
            }
        }
    }
    return dp[w];
}

518. 零钱兑换 II

自己想法

本题是求组合数（有多少种方法装满），所以递推公式是dp[j] += dp[j - coins[i]]，

并且要求顺序：外层循环是遍历物品，内层循环是遍历背包，

如果把两个for交换顺序，此时dp[j]里算出来的就是排列数！

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
 
        dp[0] = 1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

377. 组合总和 Ⅳ

自己想法

与上题不同，本题是求排列，

要求顺序：外层循环是遍历背包，内层循环是遍历物品。

此外，回溯算法：39.组合总和 (opens in a new tab) 和 40.组合总和II (opens in a new tab) 感觉这两题和本题很像， 但是本题求的是排列总和，而且仅仅是求排列总和的个数，并不是把所有的排列都列出来。 上面两题是组合总和，而且是把所有的组合都列出来。 如果本题要把排列都列出来的话，只能使用回溯算法爆搜。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (j >= nums[i]) dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}