My dynamic programming journey [2] – Coin change problem

As suggested in both Quora and StackOverflow, the coin change problem should be the second problems for beginner to solve.

There are actually multiple variations of this problem, however, my approach will be finishing the basic version first, which is:

Given a set of coins with values, find the possible way to form N (order is not considered).

Example: Given coins {2, 3, 5, 6}, find the possible way to form 10.

Approach: Top-down approach

Logic flow: Repeatedly minus coin value from N recursively until it reaches zero / negative value.

This is the parameters list of my method

int cal(int N, vector<int> coins, vector<int>mem)

  1. If N equal 0, return 1 (Which mean the coins set can successfully form N)
  2. check if mem[N] exists
  3. If yes, return mem[N]
  4. If no, set int rest = 0
  5. For each c in coins:
  6. res += cal(N - c, coins, mem)

Observation:

For f(2) and coin set {2, 5, 3, 6}

 


For f(4) and coin set {2, 5, 3, 6}

 


For f(6) and coin set {2, 5, 3, 6}