面试题 08.11. 硬币

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客

题目

难度 中等

硬币。给定数量不限的硬币，币值为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]; } }; 

执行效率为：

  大家好，我叫亓官劼（qí guān jié ），在ImapBox中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客

本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！

博主目前仅在ImapBox中写博客，唯一博客更新的地址为：亓官劼的博客