LeetCode.518 零钱兑换Ⅱ（记录）

518题是背包问题的变体，也称完全背包问题。

解法参考了该篇文章,然后对自己困惑的地方进行记录。

下面是该题的描述：

有一个背包，最大容量为 amount，有一系列物品 coins，每个物品的重量为 coins[i]，每个物品的数量无限。请问有多少种方法，能够把背包恰好装满？求出所有的装满背包的方法数。

这里和一般的背包问题的不一样在于，物品的数量是无限的，这样的问题就称为完全背包问题。因为对于一般的0-1背包问题，物体的数量是1，要么选择该物品装入背包，要么不选择该物品装入背包。

首先思考问题的状态和选择

状态有两个，就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」嘛，背包问题的套路都是这样。
第二步要明确 dp 数组的定义。

首先看看刚才找到的「状态」，有两个，也就是说我们需要一个二维 dp 数组。dp[i][j] 的定义如下：

若只使用前 i 个物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。换句话说，翻译回我们题目的意思就是：

若只使用 coins 中的前 i 个硬币的面值，若想凑出金额 j，有 dp[i][j] 种凑法。

base case 为 dp[0][…] = 0， dp[…][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为 0，那么“无为而治”就是唯一的一种凑法。
第三步，根据「选择」，思考状态转移的逻辑。这一步是很重要的，做的时候就是没有准确写出状态转移条件。

注意，我们这个问题的特殊点在于物品的数量是无限的，

如果你不把这第 i 个物品装入背包，也就是说你不使用 coins[i] 这个面值的硬币，那么凑出面额 j 的方法数 dp[i][j] 应该等于 dp[i-1][j]，继承之前的结果。

如果你把这第 i 个物品装入了背包，也就是说你使用 coins[i] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-coins[i-1]]。

首先由于 i 是从 1 开始的，所以 coins 的索引是 i-1 时表示第 i 个硬币的面值。

dp[i][j-coins[i-1]] 也不难理解，如果你决定使用这个面值的硬币，那么就应该关注如何凑出金额 j - coins[i-1]。

这里的当选择第i个物体装入背包时，那么需要考虑题目给出的条件，在文章中已经强调了好几次，这里的数量是无限的，那么当说明第i个物体可以装很多次到背包中，所以当选择第i个物品时，

dp[i][j]=dp[i-1][j]+dp[i][j-coins[i-1]],因为i是必选的，但是还可以继续选择是否装入背包

总的方法数应该是这两者之和，（选和不选两种情况的总和）

实现代码如下：

public int change(int amount, int[] coins) {

    int[][] dp = new int[coins.length + 1][amount + 1];

    for (int i = 0; i <= coins.length; i++) {

        dp[i][0] = 1;

    }

    for (int i = 1; i <= coins.length; i++) {

        for (int j = 0; j <= amount; j++) {

            if (coins[i - 1] - j > 0) {

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

            } else {

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

            }

        }

    }

    return dp[coins.length][amount];

}

然后进行代码的优化压缩，因为dp[i][j]只依赖dp[i-1][…]和dp[i][…]

public int change(int amount, int[] coins) {

    int[] dp = new int[amount + 1];

    dp[0] = 1;

    int n = coins.length;

    for (int i = 1; i <= n; i++) {

        for (int j = 0; j <= amount; j++) {

            if (j - coins[i-1]>=0) {

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

            }

        }

    }

    return dp[amount];

}

if (j - coins[i-1]>=0) {

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

}

因为当求dp[j]的时候，此时dp[j - coins[i - 1]已经求出来了，相当于dp[i][j-coins[i-1]],而此时的dp[i][j] 的值相当于上一轮的外层循环存储的值，即dp[i-1][j]的值，那么正好可以这样进行压缩。

时间复杂度和空间复杂度

这样进行压缩之后，时间复杂度为O(n*amount)，空间复杂度为O(amount).

巴特西

LeetCode.518 零钱兑换Ⅱ（记录）

518题是背包问题的变体，也称完全背包问题。

最新文章

热门文章