08.11. Coin

中文文档

Description

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents. (The result may be large, so you should return it modulo 1000000007)

Example1:

 Input: n = 5

 Output: 2

 Explanation: There are two ways:

5=5

5=1+1+1+1+1

Example2:

 Input: n = 10

 Output: 4

 Explanation: There are four ways:

10=10

10=5+5

10=5+1+1+1+1+1

10=1+1+1+1+1+1+1+1+1+1

Notes:

You can assume:

• 0 <= n <= 1000000

Solutions

Python3

Java

TypeScript

function waysToChange(n: number): number {
    const MOD = 10 ** 9 + 7;
    let coins = [1, 5, 10, 25];
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let coin of coins) {
        for (let i = coin; i <= n; ++i) {
            dp[i] += dp[i - coin];
        }
    }
    return dp.pop() % MOD;
}

...