游戲幣組合
?明的抽屜?有n個游戲幣傀缩，總?值m，游戲幣的設(shè)置有1分的屁柏，2分的啦膜，5分的有送，10分的，?在?明 所擁有的游戲幣中有些?值的游戲幣可能沒有僧家，求?共有多少種可能的游戲幣組合?式雀摘？ 輸?：輸?兩個數(shù)n(游戲幣的個數(shù))，m(總?值)八拱。 輸出：請輸出可能的組合?式數(shù)阵赠；
解題思路
暴力求解顯然是一種能解決的辦法，但是考慮到性能問題肌稻，暴力求解pass清蚀。
這里考慮使用動態(tài)規(guī)劃進行求解。首先很容易列出一個狀態(tài)表爹谭，水平方向表示總金額枷邪，豎直方向表示使用的游戲幣個數(shù)。
例如我們想求出5個硬幣組成面值為6的情況fun(5,6)诺凡，其實我們只需要針對fun(4,6-1)东揣，fun(4,6-2)，fun(4,6-5)腹泌，fun(4,6-10) 這四種情況求和即可嘶卧。也就是說只要知道用少一個硬幣得到總面值-硬幣值的結(jié)果就可以知道當(dāng)前的結(jié)果。
下面我列出了前6個數(shù)據(jù)的動態(tài)規(guī)劃表格
| 硬幣數(shù)\總面值 | 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 |
代碼邏輯實現(xiàn)
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) {
//創(chuàng)建dp數(shù)組
int[][] dp = new int[n+1][m+1];
//設(shè)定初始值
dp[0][0] = 1;
//直接使用coin代替fori循環(huán)
for (int coin : coins) {
for (int k = 1; k <= n; k++) {
for (int j = coin; j <= m; j++) {
//n個游戲幣總和為m的組合數(shù)dp[硬幣數(shù)][總面值]+=dp[硬幣數(shù)-1][m-所有的硬幣面值]
dp[k][j] += dp[k - 1][j - coin];
}
}
}
return dp[n][m];
}
}
