硬币

分类：程序员面试金典题解标签：动态规划发布于：2020-05-20 ID：8.11

难度：Medium
题目链接：https://leetcode-cn.com/problems/coin-lcci/

题目描述

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例2:

 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

说明：

注意:

你可以假设：

0 <= n (总金额) <= 1000000

解法：

本题一看就是一个动态规划问题，而且很容易和青蛙跳台阶问题联系起来，并随手写出如下递推公式：

for(int coin: coins){
    dp[i] += dp[i-coins];
}

写出如下代码进行提交，发现答案不正确，问题出在哪里呢？

class Solution {
public:
    int waysToChange(int n) {
        vector<int> coins{25, 10, 5, 1};
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        for(int i=1;i<=n;i++){
            for(int coin: coin){
                if(i < coin){
                    continue;
                }
                dp[i] += dp[i - coin];
                dp[i] %= 1000000007;
            }
        }
        return dp.back();
    }
};

自己在纸上推了一下，发现了问题所在，以 6 为例： dp[6] += dp[6-1] + dp[6-5]，意思是 6 可以在 1 的基础上加 5，也可以在 5 的基础上加 1。一个是 1+5 另一个是 5+1，问题在于这两种情况在此处是相同的。而在青蛙跳台阶的那个问题中，这两种情况是不同的。

设想我们先使用 1 分的硬币来计算构成 n 分共有多少种策略。然后加入 2 分的硬币，在 1 分的基础上，又能得到构成 n 分的一些新策略。如此，比如 3 分，只会出现 1+1+1 和 1+2 ，永远不会出现 2+1 的情况。

下面的代码实现了这种思路：

class Solution {
public:
    int waysToChange(int n) {
        vector<int> coins{25, 10, 5, 1};
        vector<int> dp(n+1, 0);
        dp[0] = 1;
        for(int coin: coins){
            for(int i=coin;i<=n;i++){
                dp[i] += dp[i - coin];
                dp[i] %= 1000000007;
            }
        }
        return dp.back();
    }
};

总结：在 DP 问题中，如果只考虑子问题的组合，那么就需要一次解决一个规模的子问题。

====

看了下别人的解答，发现这类问题有个称呼叫做：完全背包问题，给定体积各异的 n 个物品，每个物品的体积为 v_i，求填满容量为 V 的背包，有多少种选物品的方法。

设 f(i, v) 为在前 i 个物品中选择，构成体积 v 的选择数。

初始条件为：

f(0, v) = 0 且 v > 0 零个物品构成体积 v，不会有方案。
f(i, 0) = 1 物品的总体积为 0，即什么物品都不选，方案数量为 1。

递推关系为：

f(i, v) = f(i-1, v) + f(i, v - v_i)

解释如下：

f(i-1, v) 表示当前物品不选择，只在前 i-1 个物品中选择
f(i, v - v_i) 表示选取一个当前物品，余下的 v - v_i 容量的选择方案数就是 f(i, v - v_i)

按照此思路来解答本题：

class Solution {
public:
    int waysToChange(int n) {
        vector<int> coins{25, 10, 5, 1};
        unordered_map<int, vector<int>> dp;
        for(int coin: coins){
            dp[coin] = vector<int>(n+1, 0);
            dp[coin][0] = 1;
        }

        for(int i = 0; i < coins.size(); i++){
            for(int v = coins[i]; v <= n; v++){
                int num = 0;
                if(i > 0){
                    num += dp[coins[i-1]][v];
                }
                num += dp[coins[i]][v - coins[i]];
                num %= 1000000007;

                dp[coins[i]][v] = num;
            }
        }
        return dp[coins.back()].back();
    }
};

观察状态转移方程：

f(i, v) = f(i-1, v) + f(i, v - v_i)

在二维的状态矩阵中，当前位置只依赖上方的 f(i-1, v) ，以及前面的 f(i, v-v_i)。这可以使用一维的向量就够了，f(i, v) 更新前的值就是 f(i-1, v)，而 f(i, v-v_i) 处于该向量的前端。

要想把状态压缩到一维，就只能在内层循环遍历不同的 v，外层循环遍历 coins。实现方法就是本文中第二个代码片段。

LeetCode 题解

积跬步，至千里。

硬币

题目描述

解法：