> The tasks in this section contain test function calls. Please do not change this code; otherwise, the assignment may not be accepted.

The problem is to find the possible number of ways to get N cents with coins of different denominations. Imagine you have an infinite amount of coins valued `c[0], c[1],  c[2], …, c[m-1]` – some values (for example, coins of 1, 2, 5, and 10 cents; these values are stored to input as an array).

You can combine these coins to achieve `N` cents in sum. Calculate the number of possible variations.

Order does not matter, i. e. for N=10 combinations 1+2+2+5, 2+1+2+5, and 5+2+1+2 are equal.

**Example 1**: `N = 5, coins = [1,2,5]` -> 4

There are 4 ways to combine coins: 5=1+1+1+1+1, 5=1+1+1+2, 5=1+2+2, 5=5.
 
**Example 2**: `N=4, coins=[1,2,3,7]` -> 4

Answer is 4: 4=1+1+1+1, 4=2+2, 4=1+3, 4=1+1+2
 
**Example 3**: N=100, coins = [1,3,5,7,10] -> 6426

This course introduces a Dynamic Programming approach for users familiar with the syntax and data structures of the Python programming language. Dynamic programming is a necessary topic for a technical interview, as are Binary Search, Sorting Algorithms, etc. Be prepared to solve a few problems on your own. Use the hints or Solutions section if you get stuck.

Brief overview: what is Dynamic Programming, and what are the main principles.

Solve these problems using DP principles.

See the explained solutions for the problems.

Problem D. Coin Change

解答