leetcode 面试题 硬币(dp)

题目描述:

  给定数量不限的硬币,币值为25分、10分、5分和1分,编写代码计算n分有几种表示法。(结果可能会很大,你需要将结果模上1000000007)。例如n = 5的时候,结果为2(5  = 5 , 5 = 1+1+1+1+1)

题解:

  定义dp[i]表示和为i的时候有几种分法。这里状态的转移要注意,如果直接一次遍历,dp[i]  = dp[i-1] + dp[i-5] + dp[i-10] + dp[i-25]的话,会重复计算很多值。举个例子,当n = 6的时候,如果按照上述状态转移方式,那么 $dp[6] = 3 (6 = 1 +5 , 6 = 5+1 , 6 = 1+ 1 +1 +1 +1 +1)$。其中$(6 = 5+1,6 = 1+5)$就是重复的部分。那么怎么规避这种重复的情况呢?常见的去重方法是让排列有序,这里的话我们借鉴一下完全背包的模型,将多个coin的状态转移区分开,先把coin = 1的时候状态更新好,再更新coin = 5,10,25。同样以n = 6举例,先更新coin = 1的状态,此时dp[6]  =1 ;再更新coin = 5,此时dp[6] = dp[1] + dp[5] = 2。之所以将多个coin的状态区分开有效,我的理解是把coin枚举的方式有序化,这样就不会出现重复枚举的情况了。

AC代码:

class Solution {
public:
    int waysToChange(int n) {
        int dp[n+1];
        int mod = 1000000007;
        memset(dp,0,sizeof(dp));
        vector<int> coins = {1,10,5,25};
        dp[0] = 1;
        for(auto & coin : coins)
        {
            for(int i=coin;i<=n;i++) dp[i] = (dp[i] + dp[i-coin])%mod;
        }
        return dp[n];
    }
};
原文地址:https://www.cnblogs.com/z1141000271/p/12765647.html