Recursion and Dynamic Programming

Coin Change (Bottom-Up)

Build a one-dimensional table where each amount stores the fewest coins needed to make it.

Algorithm

@steps

  1. Initialize dp[0] = 0 and all other amounts to an unreachable sentinel.
  2. Scan amounts from 1 through 6.
  3. For each coin, read the earlier cell dp[amount - coin] when it exists.
  4. Write the smallest candidate into the current amount.
  5. Print both the final answer and the full DP array. @end @complexity
  • Time: O(target * coin_count)
  • Space: O(target) @end
bottom-up dynamic programming `dp[a]` is solved from already-computed smaller amounts, so every table cell has a visible dependency.

C DSA Implementation

basic.c 
#include <stdio.h>

void print_list(int values[], int count) {
  printf("[");
  for (int i = 0; i < count; i++) {
    if (i > 0) printf(", ");
    printf("%d", values[i]);
  }
  printf("]\n");
}

int main(void) {
  int coins[] = {1, 3, 4};
  int target = 6;
  int inf = target + 1;
  int dp[7];
  for (int i = 0; i <= target; i++) dp[i] = inf;
  dp[0] = 0;
  for (int amount = 1; amount <= target; amount++) {
    for (int i = 0; i < 3; i++) {
      int coin = coins[i];
      if (amount >= coin) {
        int candidate = dp[amount - coin] + 1;
        if (candidate < dp[amount]) dp[amount] = candidate;
      }
    }
  }
  printf("%d\n", dp[target]);
  print_list(dp, 7);
  return 0;
}

@end @output 2 [0, 1, 2, 1, 1, 2, 2] @end