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

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.