硬币。给定数量不限的硬币，币值为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
|
说明：
注意:
你可以假设：
完全背包问题即不限定硬币的个数去组合硬币达到指定的值。
这道题为求组合成指定数额有几种情况，我们设置 dp 数组：dp[k] 为组成 k 面额的硬币情况数。
设置基本情况：dp[0] = 1，这里 dp[0] 的含义不是 组成 0 的硬币种类为 0，二是作为完美能被一个硬币表示的情况为 1。即：
1
2
3
4
| while k - coin == 0 :
dp[k] += dp[k - coin];
=>
dp[k] += dp[0];
|
我们可以得到 dp 方程 dp[k] += dp[k-coin]；
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 mod = 1000000007;
int[] coins = {25,10,5,1};
int[] dp = new int[n+1];
dp[0] = 1;
for(int c=0; c<4; ++c){
int coin = coins[c];
for(int i=coin; i<=n; ++i){
dp[i] = (dp[i] + dp[i - coin]) % mod;
}
}
return dp[n];
}
}
|
时间复杂度为O(n)，空间复杂度为 O(n)。
coins 数组中的硬币顺序必须是由大到小。
如果硬币由小到大，我们求6的硬币情况数时，我们观察一下流程：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 前面5种情况数：dp[1,5] = [1,1,1,1,2];
coin = 1:
dp[6] += (dp[6 - coin] => dp[5] => 2);
即拿到coin(1)的情况有两种 :
coin(1,1,1,1,1) + coin(1);
coin(5) + coin(1);
coin = 5:
dp[6] += (dp[6 - coin] => dp[1] => 1);
即拿到coin（5）的情况有一种:
coin(1) + coin(5);
但是事实却是6的情况只有两种，（1，1，1，1，1，1）和（1，5）。这里是把（1，5）和（5，1）前后顺序不同的情况重复算了1次。因此我们应该去考虑硬币顺序带来的影响。
|
正确答案：
于是我们先遍历硬币，保证在考虑一枚硬币的情况时，没有较大的硬币影响，这样，我们最终每种组合情况，都是以硬币的面额大小非递减组合。保证了同样的情况，调换顺序后重复计算的情况。
这时候，我们求6的硬币情况数时，我们观察一下流程：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| coin = 1:
前面5种情况数：dp[1,5] = [1,1,1,1,1];
dp[6] += (dp[6 - coin] => dp[5] => 1);
即拿到coin(1)的情况有一种 :
coin(1,1,1,1,1) + coin(1);
coin = 5:
前面5种情况数：dp[1,5] = [1,1,1,1,2];
dp[6] += (dp[6 - coin] => dp[1] => 1);
即拿到coin（5）的情况有一种:
coin(1) + coin(5);
此时，硬币组合情况，的确为正确的情况。
|
参考：https://leetcode-cn.com/problems/coin-lcci/solution/dong-tai-gui-hua-wan-quan-bei-bao-wen-ti-by-eddiev/