硬币-背包问题 shuitang

题目

面试题 08.11. 硬币

硬币。给定数量不限的硬币,币值为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这么大的数据量,感觉就要用动态规划来做,仔细想想是一道完全背包问题,感觉好久都没遇到了……(上一次遇到还是程序设计课堂实验课上遇到过……当时感觉真难),看到评论区的各种解答,也趁此机会好好学习一波,推荐看看官方的解答背包九讲.

首先,使用 dp[i][j]表示前 i 种硬币组会成面值为 j 的所有组合的总数,然后每种硬币又可以取无限枚,所以根据完全背包的状态转移方程得出:dp[i][j] = dp[i-1][j](不取第i枚硬币) + dp[i-1][j-c[i]](取第 i 枚硬币)。

class Solution {
    const int mod = 1000000007;
public:
    int waysToChange(int n) {
        vector<int> dp(n+1,0);
        vector<int> coins = {1,5,10,25};
        dp[0] = 1;
        for(int i=0;i<coins.size();i++){
           for(int j=1;j<=n;j++){
               if(j>=coins[i]){
                   dp[j] = (dp[j] + dp[j-coins[i]])%mod;
               }  
           } 
        }
        return dp[n];
    }

};