长大后想做什么？做回小孩！

0%

程序员面试金典——硬币

发表于 分类于 Valine：
本文字数： 227

NO.08.11 硬币 中等

JaEhi4.png

和LeetCode第NO.322 零钱兑换类似的题目。

思路一：动态规划

dp[i]含义：i分有几种表示法。

初始化：dp数组大小n+1，包含0分的情况；dp[0]=1,0分只能一种表示法。

状态转移：dp[i]=dp[i]+dp[i-coin]，依次取出每个面额的硬币，如果存在[面额i-取出硬币的面额]的子问题，则将子问题的表示法种数加上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int waysToChange(int n) {
    //初始化
    int[] dp = new int[n + 1];
    dp[0] = 1;
    //硬币集
    int[] coins = {1, 5, 10, 25};
    //状态转移
    for (int coin : coins) {
        for (int i = 1; i < n + 1; i++) {
            if (i - coin >= 0) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
    }
    return dp[n];
}

时间复杂度：O(n*4) = O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github