面值凑成金额共有多少种选法(动态规划)"/>
给定硬币面值凑成金额共有多少种选法(动态规划)
题目
硬币。给定数量不限的硬币,币值为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
解题思路
- 有1,5,10,25 这几种coins,求这几种coins构成n有几种方案:
- 首先不能直接用dp[i] = dp[i - 1] + dp[i - 5] + dp[i - 10] + dp[i - 25]来计算。因为这样的结果是***每次选的顺序也计算在内,如,dp[6] = dp[1] + dp[5],其中dp[1] = 1,dp[5] = 2,选择是{1, 5} 和 {5, 1},所以结果是不正确的。
- 这里选择用两维的数组来表示选择的方案数,即:dp[i][j] 表示前 i(i < 4) 个coins构成 j 的金额共有多少种方法。
- 状态转移方程:dp[i][j] = 第i个coins不选时方案数 + 第i个coins选择t次的方案数(t * 第 i 个coins的金额小于j),即 dp[i][j] = dp[i - 1][j] + {1 < t <= j / coins[i]} (dp[i - 1][j - coins[i] * t])。
- 上述选择第 i 个coins的循环方案可以优化为 dp[i][j - coins[i]]。
- MOD = 1e7 + 9,用于结果求余。
- 得到最终状态转移方程:dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % MOD;
代码
class Solution {
public:int waysToChange(int n) {if(n == 0){return 0;}//dp打表,用dp[i][v]表示前i个***构成金额v有几种表示const int MOD = 1e9 + 7;int coins[4] = {1, 5, 10, 25};vector<vector<int>> dp(4, vector<int>(n + 1, 0));for(int i = 0; i < 4; ++i){for(int j = 0; j <= n; ++j){if(i == 0){dp[i][j] = 1;continue;}//枚举第i个***需要取几次// int t = j / coins[i];// for(int k = 0; k <= t; ++k){// dp[i][j] += dp[i - 1][j - k * coins[i]];// }//不选0,选t次dp[i][j] = dp[i - 1][j];if(j - coins[i] >= 0){dp[i][j] = (dp[i][j] + dp[i][j - coins[i]]) % MOD;} }}return dp[3][n];}
};
更多推荐
给定硬币面值凑成金额共有多少种选法(动态规划)
发布评论