游戏币组合
⼩明的抽屉⾥有n个游戏币，总⾯值m，游戏币的设置有1分的，2分的，5分的，10分的，⽽在⼩明 所拥有的游戏币中有些⾯值的游戏币可能没有，求⼀共有多少种可能的游戏币组合⽅式？ 输⼊：输⼊两个数n(游戏币的个数)，m(总⾯值)。 输出：请输出可能的组合⽅式数；
解题思路
暴力求解显然是一种能解决的办法，但是考虑到性能问题，暴力求解pass。
这里考虑使用动态规划进行求解。首先很容易列出一个状态表，水平方向表示总金额，竖直方向表示使用的游戏币个数。
例如我们想求出5个硬币组成面值为6的情况fun(5,6)，其实我们只需要针对fun(4,6-1)，fun(4,6-2)，fun(4,6-5)，fun(4,6-10) 这四种情况求和即可。也就是说只要知道用少一个硬币得到总面值-硬币值的结果就可以知道当前的结果。
下面我列出了前6个数据的动态规划表格
| 硬币数\总面值 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 1 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 1 | 1 |
| 6 | 0 | 0 | 0 | 0 | 0 | 1 |
代码逻辑实现
public class Dp {
/**
* 游戏币枚举，此处必须按从小到大顺序
*/
private static int[] coins = {1, 2, 5, 10};
public static void main(String[] args) {
int count = dp(300, 1000);
System.out.println(count);
}
public static int dp(int n, int m) {
//创建dp数组
int[][] dp = new int[n+1][m+1];
//设定初始值
dp[0][0] = 1;
//直接使用coin代替fori循环
for (int coin : coins) {
for (int k = 1; k <= n; k++) {
for (int j = coin; j <= m; j++) {
//n个游戏币总和为m的组合数dp[硬币数][总面值]+=dp[硬币数-1][m-所有的硬币面值]
dp[k][j] += dp[k - 1][j - coin];
}
}
}
return dp[n][m];
}
}
