关于算法:深入浅出零钱兑换问题背包问题的套壳

深入浅出零钱兑换问题——背包问题的套壳

前言

在本篇文章当中次要通过介绍两个算法题，从最根本的问题开始深入浅出零钱兑换问题，帮忙大家从动静布局的根源深刻了解问题当中的原理，并且学会本人剖析问题，剖析数据之间的依赖关系，通过剖析这种关系本人推导算法的优化过程，再也不怕相似于背包问题的算法题了。

零钱兑换

题目

给你一个整数数组 coins，示意不同面额的硬币；以及一个整数 amount，示意总金额。

计算并返回能够凑成总金额所需的 起码的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你能够认为每种硬币的数量是有限的。

示例

示例 1

输出：coins = [1, 2, 5], amount = 11
输入：3 
解释：11 = 5 + 5 + 1

示例 2

输出：coins = [2], amount = 3
输入：-1

状态示意和状态转移方程

在求解动静布局问题的时候通常的步骤有以下几个：

• 寻找可能示意状态的数组 dp，即咱们须要寻找dp 的含意，剖析须要用几纬数组示意具体的状态。
• 通过剖析问题，寻找动静转移公式。
• 初始化状态数组。
• 通过剖析动静转移方程，确定数组的遍历程序。

状态示意数组

在背包问题当中通常都是用一个二维数组示意数据的状态，在这个问题当中咱们应用一个二维数组 dp 示意咱们须要的状态：

dp[i][j]示意应用 coins 前i种面额的硬币示意金额等于 j 时应用的起码的金币，那么咱们最终答案就是 dp[N][amount]，他示意应用coins 数组当中所有面额的硬币示意 amount 须要的起码的硬币个数。

寻找动静转移方程

在确定了状态示意的数组之后，当初咱们就须要剖析出动静转移方程了，在这个问题当中对于每一种面额的硬币咱们都有两种抉择：选和不选，然而在这个问题当中题目曾经阐明了对于每一种货币都能够认为是有限的，如果咱们不抉择，那这种状况比较简单，然而如果抉择了这种状况就比较复杂了：

• 不选，这种状况比较简单，比方对于 dp[i][j]，如果第i 种面额的货币不抉择，那么阐明只应用前 i - 1 种面额的货币，那么 dp[i][j] = dp[i - 1][j]，也就是说明如果应用前i 种面额的货币去示意总额为 j，然而不抉择第i 种面额的货币，就相当于应用前 i-1 种货币去示意 j，那么须要的货币个数跟应用前i-1 种货币去示意 j 须要的货币数目是相等的。
• 选，这种状况看起来就比较复杂了，因为咱们须要确定是选一次，还是选两次，……，还是选 N 次，然而其实认真思考一下咱们能够应用一个相似递归的模式去解决这个问题，如果抉择那么 dp[i][j] = dp[i][j - coins[i]] + 1，咱们仔细分析一下这个公式，相当于在总金额等于j 的状况下先应用一次第 i 个面额的硬币，然而因为咱们的硬币是有限的，当初咱们还是能够抉择第 i 个硬币，相当于总金额等于 j - coins[i] 而且能够应用前 i 个硬币的状况下，须要的起码的硬币个数，这就解决了是选一次还是选 N 次的问题了，而在下面的公式当中加一的起因是应用了一次第 i 种硬币。

很显然咱们须要从下面两种状况当中抉择须要的硬币起码的一种办法，因而综合下面的后果又如下的动静转移方程：

$$
dp[i][j] = min(dp[i – 1][j], dp[i][j – coins[i]] + 1)
$$

其实下面这个问题的剖析过程跟 齐全背包 能够说是截然不同，如果你对 齐全背包 感兴趣，你能够浏览这篇文章齐全背包。

初始化状态数组

下面的问题剖析过程当中，咱们曾经剖析进去了动静转移方程，这个过程和 齐全背包 十分类似，然而这个问题比齐全背包还略微简单一点，因为不肯定可能寻找到这样一种组合凑成的总金额等于题目当中规定的数目。咱们用 -1 示意找不到这样一种组合可能示意。

• 在正式初始化之前先将 dp 数组第一行当中的数据全副初始化为 -1。
• 初始化第一行代码如下：

for (int i = 0; i * coins[0] <= amount; i++) {dp[0][i * coins[0]] = i;
}

dp数组的第一行示意只应用第一种面额的硬币，因而只有第一种硬币面额的整数倍总金额能力应用第一种硬币进行示意，而且对应的硬币个数等于 $\frac{amout}{coins[0]}$。

再看状态转移数组：

• 如果 dp[i][j - coins[i]] == -1，那么就不能通过抉择第i 种硬币进行示意，在这种状况下，咱们只能通过抉择前 i-1 一种货币进行示意，即 dp[i][j] = dp[i - 1][j]。可你你会有疑难，如果也不能应用前i-1 种物品进行示意呢？没关系，如果不能示意那么 dp[i - 1][j] == -1，那么赋值之后dp[i][j] 也等于 -1，也是不能示意的。
• 如果 dp[i][j - coins[i]] 不等于 -1，然而 dp[i - 1][j] 等于 -1，那么dp[i][j] = dp[i][j - coins[i]] + 1。
• 如果两者都不等于 -1，那么咱们就有如下的状态转移公式了：

$$
dp[i][j] = min(dp[i – 1][j], dp[i][j – coins[i]] + 1)
$$

代码

class Solution {public int coinChange(int[] coins, int amount) {int[][] dp = new int[coins.length][amount + 1];
    Arrays.fill(dp[0], -1);
    for (int i = 0; i * coins[0] <= amount; i++) {dp[0][i * coins[0]] = i;
    }
    for (int i = 1; i < coins.length; i++) {for (int j = 0; j <= amount; j++) {
        // 如果要应用对应的硬币 
        // 总金额数目必定要大于硬币的面额
        if (j >= coins[i]) {if (dp[i][j - coins[i]] == -1)
            dp[i][j] = dp[i - 1][j];
          else if (dp[i - 1][j] == -1)
            dp[i][j] = dp[i][j - coins[i]] + 1;
          else
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
        } else {
          // 否则只能应用前 i-1 种硬币
          dp[i][j] = dp[i - 1][j];
        }
      }
    }
    return dp[coins.length - 1][amount];
  }
}

下面的代码体现的就是 齐全背包 的思维，在题目当中硬币能够应用有限次，如果只能应用一次的话，问题就转换成01 背包 了，那么动静转移方程就为：

$$
dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – coins[i]] + 1)
$$

单行数组优化

依据动静转移方程 $dp[i][j] = min(dp[i – 1][j], dp[i][j – coins[i]] + 1)$，咱们能够失去 dp 数组当中数据之间的依赖关系，他们的关系如上图所示，dp[i][j]依赖的数据为它上一行同列的地位，和第 i 行后面的某些数据，事实上咱们能够应用单行数组去进行实现，咱们应用的循环还是一样的，然而应用的数组有所变动，从之前的二维数组变成一维数组。当咱们遍历到单行数组第 j 个数据的时候，第 j 个数据还是上一行的状态，然而单行数组的下标从 0 到 j-1 的地位数据的状态曾经从上一行更新了，这些数据的状态相当于二维数组的 dp[i] 这一行的状态，而这正好能够满足动静转移方程的需要，因为在动静转移方程当中，dp[i-1][j]依赖的数据全副符合条件，单行数组当中的下标为 j 数据等于 dp[i][j]，单行数组下标为x 的数据等于dp[i][x]，其中 $0 \le x \le j$，这里你能够联合代码、文字和图片进行了解，了解成果会更加好一点。

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];
    Arrays.fill(dp, -1);
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++)  {if (dp[j - coins[i]] != -1) {if (dp[j] == -1) {dp[j] = dp[j - coins[i]] + 1;
          }else
            dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
      }
    }
    return dp[amount];
  }
}

另一种角度思考问题

在下面的文章当中，咱们是应用 - 1 去示意不可能找到一个组合满足总金额数目。咱们能够先将数组当中所有的数据全副初始化成amount + 1，这个是硬币的上界，如果咱们全副应用一块的硬币进行兑换，后果是amount，因而最大的值不会超过amount + 1，因为在动静转移方程当中求的是最小值，因而在进行状态转移的时候不会抉择这个值，因而上面的代码也是正确的！！！

class Solution {public int coinChange(int[] coins, int amount) {
    int max = amount + 1;
    int[] dp = new int[amount + 1];
    for (int j = 0; j < dp.length; j++) {dp[j] = max;
    }
    dp[0] = 0;
    for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {if (dp[j - coins[i]] != max) {dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
        }
      }
    }
    return dp[amount] == max ? -1 : dp[amount];
  }
}

零钱兑换 II

题目

给你一个整数数组 coins 示意不同面额的硬币，另给一个整数 amount 示意总金额。

请你计算并返回能够凑成总金额的硬币组合数。如果任何硬币组合都无奈凑出总金额，返回 0。

假如每一种面额的硬币有有限个。

题目数据保障后果合乎 32 位带符号整数。

示例

示例 1

输出：amount = 5, coins = [1, 2, 5]
输入：4
解释：有四种形式能够凑成总金额：5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2

输出：amount = 3, coins = [2]
输入：0
解释：只用面额 2 的硬币不能凑成总金额 3。

状态示意和状态转移方程

状态示意数组

在这个问题当中咱们也是应用一个二维数组示意咱们的状态 dp[i][j]。这个示意应用前i 个硬币，总金额为 j 的状况下，可能找到多少种组合形式，是硬币的和等于总金额数。

在这道题目当中咱们也能够应用无数次硬币，因而这也是一个 齐全背包 问题。

寻找动静转移方程

对于每一种硬币同样的有两种状况抉择和不抉择，每一种状况都有不同的组合，因而最终的组合数目就是将这两个后果相加：

• 抉择，在这个状况下咱们可能取得不同的组合数就是 dp[i][j - coins[i]]，这个代码的含意就是抉择一次第i 个硬币，因为有无数个硬币，因而这个后果就等于应用前 i 个硬币组合总金额为 j-coins[i] 时，一共有多少个组合。
• 不抉择，如果不进行抉择，那么就相当于应用前 i - 1 个硬币，组合总金额为 j 时，一共有多少个组合。

因而最终的组合数的个数就是下面两种形式的不同组合个数相加，因而咱们的动静转移方程为：

$$
dp[i][j] = dp[i – 1][j] + dp[i][j – coins[i]];
$$

初始化状态数组

在初始化 dp 数组的第一行的时候，只有是第一个硬币的整数倍的总金额能力进行匹配，如果不能匹配，那么不同的组合的数目就等于 0，可能进行匹配的组合数也只有一个，那就是应用的硬币全是第一种硬币。在这里须要留神的是当总金额等于 0 的时候，也是有一种组合形式的，那就是没有一个硬币，这也是一种组合形式，就相当于汇合的空基，因而初始化代码如下：

for (int i = 0; i * coins[0] <= amount; i++) {dp[0][i * coins[0]] = 1;

代码

class Solution {public int change(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1];
    // dp[i][j] 的含意：前 i 个钱 容量 j 有多少种办法
    for (int i = 0; i * coins[0] <= amount; i++) {dp[0][i * coins[0]] = 1;
    }
    for (int i = 1; i < coins.length; i++) {for (int j = 0; j <= amount; j++) {if (j >= coins[i]) {dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
        } else
          dp[i][j] = dp[i - 1][j];
      }
    }
    return dp[coins.length - 1][amount];
  }
}

其实这道题也有对应的 01 背包 问题，在这道题目当中是 齐全背包 问题的变种，如果所有的硬币只可能应用一次的话，那么动静转移方程如下：

$$
dp[i][j] = dp[i – 1][j] + dp[i – 1][j – coins[i]];
$$

单行数组优化

class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];
    // dp[i][j] 的含意：前 i 个钱 容量 j 有多少种办法
    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];
  }
}

这个优化的原理和第一题也是一样的，通过剖析动静转移方程，看单行数组是否可能满足动静转移方程的要求，如果可能满足的话，那就可能进行单行数组优化，反之不能进行优化，而在这个问题当中，数据依赖关系和第一题是一样的，dp[i][j]依赖的数据是 dp[i - 1][j] 和dp数组第 i 行前 j - 1 个数据，依据第一题的剖析，咱们是能够应用单行数组进行优化的！！！

总结

在本篇文章当中次要给大家介绍了两道 零钱兑换 的问题，在本文当中的这两道题目都是属于 齐全背包 的变种，如果要彻底弄懂这个问题的话就须要好好剖析动静转移方程和数据之间的依赖关系，通过剖析数据之间的依赖关系，咱们本人也能够从零推导优化过程。在这两道问题当中硬币都能够应用无数次，如果将可能应用的硬币只可能应用一次的话，那么这个问题就变成 01 背包 的变种问题了。

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。