Skip to content

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

Solution 1: Dynamic Programming

Thinking

Make amount \(n\) with coins \(25,10,5,1\), order ignored. Nested loops over counts work, and they are the unbounded knapsack recurrence.

\(f[i][j]\) is the number of ways with the first \(i\) coins. The transition is \(f[i][j]=f[i-1][j]+f[i][j-c_i]\) when \(j\ge c_i\).

Four coin types fit a \(5\times(n+1)\) table; \(f[0][0]=1\) is the empty way. Reduce modulo \(10^9+7\).

We define \(f[i][j]\) as the number of ways to make up the total amount \(j\) using only the first \(i\) types of coins. Initially, \(f[0][0]=1\), and the rest of the elements are \(0\). The answer is \(f[4][n]\).

Considering \(f[i][j]\), we can enumerate the number of the \(i\)-th type of coin used, \(k\), where \(0 \leq k \leq j / c_i\), then \(f[i][j]\) is equal to the sum of all \(f[i−1][j−k \times c_i]\). Since the number of coins is infinite, \(k\) can start from \(0\). That is, the state transition equation is as follows:

\[ f[i][j] = f[i - 1][j] + f[i - 1][j - c_i] + \cdots + f[i - 1][j - k \times c_i] \]

Let \(j = j - c_i\), then the above state transition equation can be written as:

\[ f[i][j - c_i] = f[i - 1][j - c_i] + f[i - 1][j - 2 \times c_i] + \cdots + f[i - 1][j - k \times c_i] \]

Substitute the second equation into the first equation to get:

\[ f[i][j]= \begin{cases} f[i - 1][j] + f[i][j - c_i], & j \geq c_i \\ f[i - 1][j], & j < c_i \end{cases} \]

The final answer is \(f[4][n]\).

The time complexity is \(O(C \times n)\), and the space complexity is \(O(C \times n)\), where \(C\) is the number of types of coins.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def waysToChange(self, n: int) -> int:
        mod = 10**9 + 7
        coins = [25, 10, 5, 1]
        f = [[0] * (n + 1) for _ in range(5)]
        f[0][0] = 1
        for i, c in enumerate(coins, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= c:
                    f[i][j] = (f[i][j] + f[i][j - c]) % mod
        return f[-1][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int waysToChange(int n) {
        final int mod = (int) 1e9 + 7;
        int[] coins = {25, 10, 5, 1};
        int[][] f = new int[5][n + 1];
        f[0][0] = 1;
        for (int i = 1; i <= 4; ++i) {
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= coins[i - 1]) {
                    f[i][j] = (f[i][j] + f[i][j - coins[i - 1]]) % mod;
                }
            }
        }
        return f[4][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int waysToChange(int n) {
        const int mod = 1e9 + 7;
        vector<int> coins = {25, 10, 5, 1};
        int f[5][n + 1];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= 4; ++i) {
            for (int j = 0; j <= n; ++j) {
                f[i][j] = f[i - 1][j];
                if (j >= coins[i - 1]) {
                    f[i][j] = (f[i][j] + f[i][j - coins[i - 1]]) % mod;
                }
            }
        }
        return f[4][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func waysToChange(n int) int {
    const mod int = 1e9 + 7
    coins := []int{25, 10, 5, 1}
    f := make([][]int, 5)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    f[0][0] = 1
    for i := 1; i <= 4; i++ {
        for j := 0; j <= n; j++ {
            f[i][j] = f[i-1][j]
            if j >= coins[i-1] {
                f[i][j] = (f[i][j] + f[i][j-coins[i-1]]) % mod
            }
        }
    }
    return f[4][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function waysToChange(n: number): number {
    const mod = 10 ** 9 + 7;
    const coins: number[] = [25, 10, 5, 1];
    const f: number[][] = Array.from({ length: 5 }, () => Array(n + 1).fill(0));
    f[0][0] = 1;
    for (let i = 1; i <= 4; ++i) {
        for (let j = 0; j <= n; ++j) {
            f[i][j] = f[i - 1][j];
            if (j >= coins[i - 1]) {
                f[i][j] = (f[i][j] + f[i][j - coins[i - 1]]) % mod;
            }
        }
    }
    return f[4][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    func waysToChange(_ n: Int) -> Int {
        let mod = Int(1e9 + 7)
        let coins = [25, 10, 5, 1]
        var f = Array(repeating: Array(repeating: 0, count: n + 1), count: 5)
        f[0][0] = 1

        for i in 1...4 {
            for j in 0...n {
                f[i][j] = f[i - 1][j]
                if j >= coins[i - 1] {
                    f[i][j] = (f[i][j] + f[i][j - coins[i - 1]]) % mod
                }
            }
        }
        return f[4][n]
    }
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Row \(i\) reads only row \(i-1\) and smaller \(j\) on the same row, so the first index can be dropped.

A one-dimensional array updated in increasing \(j\) keeps the same recurrence in \(O(n)\) space.

We notice that the calculation of \(f[i][j]\) is only related to \(f[i−1][..]\). Therefore, we can remove the first dimension and optimize the space complexity to \(O(n)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def waysToChange(self, n: int) -> int:
        mod = 10**9 + 7
        coins = [25, 10, 5, 1]
        f = [1] + [0] * n
        for c in coins:
            for j in range(c, n + 1):
                f[j] = (f[j] + f[j - c]) % mod
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int waysToChange(int n) {
        final int mod = (int) 1e9 + 7;
        int[] coins = {25, 10, 5, 1};
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int c : coins) {
            for (int j = c; j <= n; ++j) {
                f[j] = (f[j] + f[j - c]) % mod;
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int waysToChange(int n) {
        const int mod = 1e9 + 7;
        vector<int> coins = {25, 10, 5, 1};
        int f[n + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int c : coins) {
            for (int j = c; j <= n; ++j) {
                f[j] = (f[j] + f[j - c]) % mod;
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func waysToChange(n int) int {
    const mod int = 1e9 + 7
    coins := []int{25, 10, 5, 1}
    f := make([]int, n+1)
    f[0] = 1
    for _, c := range coins {
        for j := c; j <= n; j++ {
            f[j] = (f[j] + f[j-c]) % mod
        }
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function waysToChange(n: number): number {
    const mod = 10 ** 9 + 7;
    const coins: number[] = [25, 10, 5, 1];
    const f: number[] = new Array(n + 1).fill(0);
    f[0] = 1;
    for (const c of coins) {
        for (let i = c; i <= n; ++i) {
            f[i] = (f[i] + f[i - c]) % mod;
        }
    }
    return f[n];
}

Comments