面试题 08.11. 硬币

难度中等82

硬币。给定数量不限的硬币，币值为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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int waysToChange(int n) {
        //dp
        int result=0;
        //完全背包问题: 25 10 5 1 4个物品
        //dp[0][0]=1
        //dp[i][j]=dp[i-1][j]+dp[i-1][j-val[i]]+dp[i-1][j-val[i]*2]...+dp[i-1][j-val[i]*k],(k+1)*val[i]>=j>=k*val[i] 
        //dp[i][j-val[i]]=dp[i-1][j-val[i]]+dp[i-1][j-val[i]*2]....+dp[i-1][j-val[i]*k]
        //上下相减:
        //dp[i][j]-dp[i][j-val[i]]=dp[i-1][j]
        //因此:
        //dp[i][j]=dp[i-1][j]+dp[i][j-val[i]];
        //没有优化的版本:
        vector<int>val={1,5,10,25};
        vector<int>temp(n+2,0);
        vector<vector<int>>dp(val.size(),temp);
        dp[0][0]=1;
        for(int i=0;i<4;i++){
            dp[i][0]=1;//不管用几种硬币组成0元只有一种方法
        }
        for(int i=0;i<n+1;i++){
            dp[0][i]=1;//只用一种硬币(1)当然只有一种方法
        }

        
        for(int i=1;i<val.size();i++){
            for(int j=1;j<n+1;j++){
                if(j>=val[i])
                    dp[i][j]=dp[i-1][j]% 1000000007+dp[i][j-val[i]]% 1000000007;
                else{
                    dp[i][j]=dp[i-1][j]% 1000000007;
                }
            }
        }
        return dp[3][n]% 1000000007;
    }
};

//上面的是没有简化过的版本,因为不难发现j是递增的,因此存储空间可以复用,因此可以把二维降到一维

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int waysToChange(int n) {
        //dp
        int result=0;
        //完全背包问题: 25 10 5 1 4个物品
        //dp[0][0]=1
        //dp[i][j]=dp[i-1][j]+dp[i-1][j-val[i]]+dp[i-1][j-val[i]*2]...+dp[i-1][j-val[i]*k],(k+1)*val[i]>=j>=k*val[i] 
        //dp[i][j-val[i]]=dp[i-1][j-val[i]]+dp[i-1][j-val[i]*2]....+dp[i-1][j-val[i]*k]
        //上下相减:
        //dp[i][j]-dp[i][j-val[i]]=dp[i-1][j]
        //因此:
        //dp[i][j]=dp[i-1][j]+dp[i][j-val[i]];
        //
        //降维到一维的版本:
        //dp[j]=dp[j]+dp[j-val[i]];
        vector<int>val={1,5,10,25};
        vector<int>dp(n+2,1);
        dp[0]=1;
        for(int i=1;i<val.size();i++){
            for(int j=1;j<=n;j++){
                if(j>=val[i])
                    dp[j]=dp[j]%1000000007+dp[j-val[i]]%1000000007;
            }
        }
        return dp[n]%1000000007;

    }
};