硬币

2021-01-09

给定数量不限的硬币，币值为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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

背包问题：

用 $f(i,v)$ 来表示前 $i$ 种面值的硬币构成面值为 $v$ 的方案数量，用 $c_i$来表示第 i种面值的硬币的面值。

我们可以从 $f(i - 1, v - 0 \times c_i)$,$f(i - 1, v - 1 \times c_i)$, $f(i - 1, v - 2 \times c_i)\cdots$ $f(i - 1, v - k \times c_i)$转移得到，它们表示第 $i$ 个面值的硬币选 $0, 1, 2 \cdots k$ 个的时候，构成面值为 $v$ 的方案数量，其中 $k$ 为满足 $v - k \times c_i \geq 0$的最大整数。于是我们可以推导出这样的动态规划转移方程：

$f(i, v)=\sum_{j=0}^{k} f(i-1, v-j \times c i), k=\left\lfloor\frac{v}{c i}\right\rfloor$

举个例子: 假设这里 $c = {1, 5, 10, 25}$，在$i = 4$ 的时候，$c_i = 25$（假设下标从 $1$ 开始），如果我们要求前 $4$ 种面值构成 $90$ 的方案数量，可以这么写：

$f(4, 90) = f(3, 90) + f(3, 90 - 25) + f(3, 90 - 2 \times 25) + f(3, 90 - 3 \times 25)$

优化时间复杂度：

avatar

$f(i, v)=f(i-1, v)+f\left(i-1, v-c_{i}\right)+f\left(i-1, v-2 c_{i}\right) \cdots f\left(i-1, v-k c_{i}\right)$

共 $k + 1$ 项，其中 $k = \lfloor \frac{v}{c_i} \rfloor$ 那么我们可以得到使用 $v - c_i$替换 $v$，得到：

$f\left(i, v-c_{i}\right)=f\left(i-1, v-c_{i}\right)+f\left(i-1, v-2 c_{i}\right)+f\left(i-1, v-3 c_{i}\right) \cdots f\left(i-1, v-k c_{i}\right)$

共 $k$ 项。注意到上面两个方程中标成红色的 $k$ 项是完全相同的，于是我们可以用下面式子的左半部分 $f(i, v - c_i)$等价替换上面式子红色的 $k$ 项，得到化简后的转移方程：

$f(i, v) = f(i - 1, v) + f(i, v - c_i)$

不进行任何优化

class Solution{
    static final int mod = 1000000007;
    public int waysToChange(int n) {
        int[] coins = new int[]{0, 25, 10, 5, 1};
        int[][] dp = new int[5][n + 1];
        for (int i = 0; i <= 4; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k * coins[i] <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k * coins[i]] % mod;
                }

            }
        }
        return dp[4][n];
    }
}

优化时间复杂度

class Solution{
    public int waysToChange1(int n) {
        int[] coins = new int[]{0, 25, 10, 5, 1};
        int[][] dp = new int[5][n + 1];

        for (int i = 0; i <= 4; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= n; j++) {
                if (j < coins[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] += (dp[i - 1][j] + dp[i][j - coins[i]]) % mod;
                }
            }
        }
        return dp[4][n];
    }
}

再优化空间复杂度

class Solution {

    static final int mod = 1000000007;

    public int waysToChange(int n) {
        int[] coins = new int[]{25, 10, 5, 1};
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int c = 0; c < 4; ++c) {
            int coin = coins[c];
            for (int i = coin; i <= n; ++i) {
                f[i] = (f[i] + f[i - coin]) % mod;
            }
        }
        return f[n];
    }

}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-lcci/solution/ying-bi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。