Dynamic Programming Mastery: 11 Classic Problems Solved with Recurrences & C Code

General Dynamic Programming Approach

Dynamic programming solves problems by identifying the substructure (state) , solving overlapping subproblems (via memoization or bottom-up tabulation), and reconstructing an optimal solution. The article contrasts DP with backtracking (which lacks a universal framework) and divide-and-conquer (which creates new subproblems each recursion). A memoization (top-down) variant is also described: initialize a table with a sentinel value, compute and store on first visit, then reuse.

1. Coin Change (Minimum Coins)

Problem: Given unlimited coins of denominations (e.g., 1, 3, 5), find the minimum number of coins to make amount total.

Recurrence: sum[k] = min(sum[k - coin[i]]) + 1 for all coins where k - coin[i] >= 0, with sum[0] = 0.

Implementation: A state struct stores nCoin (min coins), lastSum (previous amount), and addCoin (coin used) for path reconstruction. Bottom-up loops fill sum[1..total].

typedef struct { int nCoin; int lastSum; int addCoin; } state;
state *sum = malloc(sizeof(state)*(total+1));
for(i=0;i<=total;i++) sum[i].nCoin = INF;
sum[0].nCoin = 0; sum[0].lastSum = 0;
for(i=1;i<=total;i++)
  for(j=0;j<n;j++)
    if(i-coin[j]>=0 && sum[i-coin[j]].nCoin+1 < sum[i].nCoin) {
      sum[i].nCoin = sum[i-coin[j]].nCoin+1;
      sum[i].lastSum = j;
      sum[i].addCoin = coin[j];
    }

Extension: Apple Collection Grid

An N x M grid with apples A[i][j]. Move only right/down from (1,1) to (N,M), maximize apples. State M[i][j] = max(M[i-1][j], M[i][j-1]) + A[i][j] with boundary conditions.

Extension: Assembly Line Scheduling (CLRS 15.1)

2. Edit Distance / String Similarity

Operations: delete, insert, replace (each cost 1). Distance = minimum operations to make strings equal.

Recurrence for m[i][j] (distance of prefixes length i, j):

If last chars equal: m[i][j] = m[i-1][j-1] Else: m[i][j] = min(m[i-1][j-1]+1, m[i-1][j]+1, m[i][j-1]+1) Overlapping subproblems are prefixes S[1..i], T[1..j]. C code shifts indices by 1 for 0-based arrays.

Applications:

Substring matching: modify two lines in the DP to allow free prefix/suffix skipping.

Longest Common Subsequence (LCS): convert match cost to maximize length.

Reference: Skiena's Algorithm Design Manual 8.2.4.

3. Longest Common Subsequence (LCS)

Standard DP from CLRS. For sequences X[1..m], Y[1..n], let c[i][j] be LCS length of prefixes, b[i][j] direction.

Recurrence:

If X[i]==Y[j]: c[i][j] = c[i-1][j-1] + 1, b[i][j] = diagonal Else if c[i-1][j] >= c[i][j-1]: c[i][j] = c[i-1][j], b[i][j] = up Else: c[i][j] = c[i][j-1],

b[i][j] = left

Extension: Output all LCS – when c[i-1][j] == c[i][j-1], both up and left are valid; recurse to enumerate all paths. Upper bound O(mn).

Extension: LIS via LCS – sort the sequence to get target 1..max; LCS with original yields LIS. For non-decreasing, duplicate each value in the sorted sequence.

4. Longest Increasing Subsequence (LIS)

O(n²) DP: lis[k] = length of LIS ending at s[k]. lis[k] = max(lis[i]+1) for i<k and s[i] < s[k]. Track prev for reconstruction.

typedef struct { int length; int prev; } state;
state *a = malloc(sizeof(state)*n);
for(i=0;i<n;i++) { a[i].length=1; a[i].prev=-1; }
for(i=1;i<n;i++)
  for(j=0;j<i;j++)
    if(array[i]>array[j] && a[i].length < a[j].length+1) {
      a[i].length = a[j].length+1;
      a[i].prev = j;
    }

O(n log n) Optimization: Maintain MaxV[len] = minimum tail value of an increasing subsequence of length len. MaxV is strictly increasing, so binary search finds the insertion point for each new element. This reduces time to O(n log n).

int lis_ologn(int *array, int length) {
  int *MaxV = malloc(sizeof(int)*(length+1));
  MaxV[0] = -1; MaxV[1] = array[0];
  int max_len = 1;
  for(i=1;i<length;i++) {
    int left=1, right=max_len, mid;
    while(left<right) {
      mid = (left+right)/2;
      if(MaxV[mid] <= array[i]) left = mid+1;
      else right = mid;
    }
    if(MaxV[right] > array[i] && MaxV[right-1] < array[i]) MaxV[right] = array[i];
    else if(MaxV[right] < array[i]) { MaxV[right+1] = array[i]; max_len++; }
  }
  return max_len;
}

5. Maximum Subarray Sum / Product

Maximum Sum (Kadane): maxendinghere = max(maxendinghere + a[i], a[i]); maxsofar = max(maxsofar, maxendinghere). O(n) time, O(1) space.

int max_array_v4(int *array, int length) {
  int maxsofar = INT_MIN, maxendinghere = 0;
  for(i=0;i<length;i++) {
    maxendinghere = max(maxendinghere + array[i], array[i]);
    maxsofar = max(maxsofar, maxendinghere);
  }
  return maxsofar;
}

Extension 1: Maximum product of positive floats – take logarithms, convert to max sum problem.

Extension 2: Maximum product with negatives/zeros – track both maxendinghere and minendinghere because a negative times a negative becomes positive.

new_max = max(max*arr, min*arr, arr);
new_min = min(max*arr, min*arr, arr);
maxsofar = max(maxsofar, new_max);

6. Matrix Chain Multiplication

Given chain A1..An with dimensions p_{i-1} x p_i, find parenthesization minimizing scalar multiplications.

Recurrence: m[i][j] = 0 if i=j; else min_{i<=k<j} (m[i][k] + m[k+1][j] + p_{i-1}*p_k*p_j).

Bottom-up DP fills m[1][n] and records split points. Memoized top-down version from CLRS 15.1 is also shown.

7. 0-1 Knapsack

Items with value v_i, weight w_i, capacity W. DP table c[i][j] = max value using first i items with capacity j.

Recurrence:

If w_i > j: c[i][j] = c[i-1][j] Else: c[i][j] = max(c[i-1][j-w_i] + v_i, c[i-1][j]) Contrast with fractional knapsack (greedy by value/weight). C code image provided.

8. Shortest Path with Vertex Costs

Undirected graph, each vertex i has cost S(i), initial money M. Find shortest path from 1 to N where total cost ≤ M; if multiple, pick cheapest.

State: Min[i][j] = shortest distance to vertex i with j money remaining after paying S(i).

Modified Dijkstra over state space (vertex, money). Pseudocode:

for all (i,j) Min[i][j]=INF, state=unvisited;
Min[0][M]=0;
while(1) {
  pick unvisited (k,l) with smallest Min[k][l];
  if Min[k][l]==INF break;
  state[k][l]=visited;
  for each neighbor p of k:
    if l-S[p]>=0 && Min[p][l-S[p]] > Min[k][l]+Dist[k][p]
      Min[p][l-S[p]] = Min[k][l]+Dist[k][p];
}
answer = min_j Min[N-1][j]; if tie, pick largest j.

9. Tiling with Dominoes (State Compression DP)

Cover n x m board with 1x2 tiles. DP row by row; state is an m -bit mask where bit=1 means a vertical tile occupies that cell in the next row.

DFS generates all valid horizontal placements within a row given the forced vertical tiles (from previous row's mask). Transition: next row's forced mask = bitwise NOT of current mask (within m bits).

C code uses dp[row][state] counting ways. Optimization: compress the smaller dimension to reduce state space.

void dfs(int row, int state, int pos, long long pre_num) {
  if(pos==m) { dp[row][state] += pre_num; return; }
  dfs(row, state, pos+1, pre_num); // leave empty
  if(pos<=m-2 && !(state&(1<<pos)) && !(state&(1<<(pos+1))))
    dfs(row, state|(1<<pos)|(1<<(pos+1)), pos+2, pre_num); // place horizontal
}
// main loops rows, iterates previous states, calls dfs with (~prev_state) & ((1<<m)-1)

10. Work Allocation (Linear Partition)

Partition n books (pages s_i) into k contiguous groups to minimize the maximum group sum.

Recurrence:

M[n][k] = min_{1<=i<=n} max(M[i][k-1], sum_{j=i+1}^n s_j)

.

Base: M[1][k] = s_1, M[n][1] = sum_{i=1}^n s_i. Bottom-up computation yields optimal partition. Application: parallel task scheduling to minimize makespan.

11. Three-Pass Apple Picking

Three trips from (1,1) to (N,M) and back, collecting apples only on first visit. Second trip (up/left) is equivalent to another down/right path. Paths can be reordered to non-crossing left/middle/right.

State: Max[y][i][j][k] = max apples at row y with three paths at columns i <= j <= k. Transition enumerates next columns i' in [i..j'], j' in [j..k'], k' in [k..M]. Overlap handled by a visited flag per cell. Final answer Max[N][M][M][M].

References

CLRS Chapter 15 (Dynamic Programming), Chapter 16 (Greedy Algorithms)

Skiena, Algorithm Design Manual Chapter 8

Bentley, Programming Pearls

Beauty of Programming

POJ 2411 & Beauty of Programming 4.2 (Tiling)

Maximum Continuous Subsequence Product

Dynamic Programming: From novice to advanced

Appendix: Additional DP Problems

Bitonic Euclidean TSP (CLRS 15-1)

Neat Printing / Text Justification (CLRS 15-4)

Viterbi Algorithm (Hidden Markov Models)

Maximum Profit Scheduling (CLRS 15-7)

Skiena Chapter 8 interview questions:

8-24: Coin change (covered in Problem 1)

8-25: Maximum subarray sum (covered in Problem 5)

8-26: Paper cutting with letters on both sides – solved via max flow on a bipartite network