游戲幣組合

?明的抽屜?有n個游戲幣，總?值m，游戲幣的設(shè)置有1分的，2分的，5分的，10分的，?在?明 所擁有的游戲幣中有些?值的游戲幣可能沒有，求?共有多少種可能的游戲幣組合?式？ 輸?：輸?兩個數(shù)n(游戲幣的個數(shù))，m(總?值)。 輸出：請輸出可能的組合?式數(shù)；

解題思路

暴力求解顯然是一種能解決的辦法，但是考慮到性能問題，暴力求解pass。

這里考慮使用動態(tài)規(guī)劃進(jìn)行求解。首先很容易列出一個狀態(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ī)劃表格

代碼邏輯實現(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];
    }
}