题目描述

题目链接

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

示例1：

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

示例2：

1
2
3
4
5
6
7
 输入: 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

算法1

(动态规划) $O(n^2)$

分析题意，不难看出这是一道经典的完全背包模型题

完全背包模型为：

  • 共有 i种物品，从中选出若干个装满体积为j的背包，所能达到的最大价值，每种物品的体积为vi, 价值为 wi
  • 每种物品可以选0~无限个

完全背包的思考方式如下：

  • 首先，要认识到每种方案的选择都是一类状态的结果，因此很容易想到需要使用动态规划
  • 其次，按照动态规划的思考路线，首先思考动态规划的递推数组含义：
    • 由于数组是包含了物品种类i，物品体积j两个因素，因此很容易想到需要使用二维数组来进行表示
    • f[i][j]表示，从 i 种物品种选出体积为 j的方案的价值，在本题中，可以转换为：从前 i 种硬币中，选出组合为 j 的方案数
    • 考虑递推关系，当选择第 i 种硬币时，可以选 0 个，1 个， 2 个， …，
      • 可得到递推关系式为：
        f[i][j] = f[i - 1][j] + f[i - 1][j - vi] + f[i - 1][j - 2vi] + f[i - 1][j - 3vi] + ...
        可以看到是一个具有明显递推性质的公式，那么尝试递推， 将j 替换为 j - vi：
        f[i][j - vi] = f[i - 1][j - vi] + f[i - 1][j - 2vi] + f[i -1][j - 3vi] + ...
      • 通过递推关系，可以得到最终的递推式：
        f[i][j] = f[i - 1][j] + f[i][j - 1]
  • 最终，根据我们得到的递推式，可以写出动态规划的解题方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int waysToChange(int n) {
        int coins[5] = {0, 1, 5, 10, 25};
        const int MOD = 1000000007;
        vector<vector<int>> f(5, vector<int> (n + 1));
        f[0][0] = 1;
        for(int i = 1; i <= 4; i ++)
            for(int j = 0; j <= n; j ++)
            {
                f[i][j] = f[i - 1][j];
                if( j >= coins[i])
                    f[i][j] = (f[i][j] + f[i][j - coins[i]]) % MOD;
            }

        return f[4][n];
    }
};

算法2

(动态规划， 空间优化版本) $O(n^2)$

朴素版本的动态规划使用了$O(n^2)$的空间，但是这种空间有很多冗余，是可以进行优化的

观察我们的递推公式，在第一维 f[i]中，所有的f[i]都依赖于前一个f[i - 1]，因此可以将f[i]这一维优化掉:

f[i][j] = f[i - 1][j] + f[i][j - vi] 优化为：
f[j] = f[j] + f[j - vi]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    const int MOD = 1000000007;
    int waysToChange(int n) {
        int coins[5] = {0, 1, 5, 10, 25};

        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= 4; i ++)
            for(int j = 0; j <= n; j ++)
            {
                if( j >= coins[i])
                    f[j] = (f[j] + f[j - coins[i]]) % MOD;
            }


        return f[n];
    }
};