LeetCode 面試題 08.11. 硬币 多種解法 完全背包問題

面試題 08.11. 硬币

  大家好，我叫亓官劼（qí guān jié ）

題目

難度 中等

硬币。給定數量不限的硬币，币值為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

題解一：暴力

  這題題目要求給我們一個數n，讓我們使用4中硬币來湊到這個n，這裡硬币有25分、10分、5分和1分，讓我們求的是可以有多少種方法來湊到n。映入眼簾的當然就是直接暴力的做法了。不過這個代碼是肯定不過的，因為時間複雜度為O(N^4)

代碼為：

class Solution {
public:
    int waysToChange(int n) {
        int ans = 0;
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= n/5; j++ ){
                for(int k = 0; k <= n/10; k++){
                    for(int u = 0; u <= n/25; u++){
                        if(i + j*5 + k*10 + u*25 == n){
                            ans = (ans + 1) % 1000000007;
                        }
                    }
                }
            }
        }
        return ans;
    }
};      

題解二：dp，完全背包問題

  這題很明顯是一個完全背包問題，一共有四種物品，讓我們拿重量為N。但是我們要注意，這裡的順序是可以颠倒的，是以這裡要将物品的循環放在外循環中，來避免出現順序颠倒的情況。

完整的題解代碼如下：

class Solution {
public:
    int waysToChange(int n) {
        int dp[1000001];
        int coins[4] = {25,10,5,1};
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        for(int i = 0 ; i < 4; i++){
            int coin = coins[i];
            for(int j = coin; j <= n; j++){
                dp[j] = (dp[j] + dp[j-coin]) % 1000000007;
            }
        }
        return dp[n];
    }
};      

執行效率為：