0/1 Knapsack: dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]])
Unbounded Knapsack: 1D optimization: dp[w] = max(dp[w], value[i] + dp[w-weight[i]])
Matrix Chain: interval DP over (i,j) with split k minimizing cost.
Complexities: 0/1 O(nC), Unbounded O(nC), Matrix Chain O(n³), common space optimizations.

0/1 vs Unbounded loop order

Matrix Chain split tree

0/1 Knapsack

2D Tabulation

Pseudocode

1function knap01(weights, values, W):
2  n = len(weights)
3  dp = array(n+1, W+1, 0)
4  for i in 1..n:
5    for w in 0..W:
6      dp[i][w] = dp[i-1][w]
7      if w >= weights[i-1]:
8        dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w-weights[i-1]])
9  return dp[n][W]

Interactive: Build the 0/1 Knapsack Table

Tip: Change weights, values, and capacity to explore different tables and decisions.

WeightsValuesCapacity

0/1 Knapsack Table

Speed

i/w	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1 (w=2, v=3)	0	0	0	0	0	0	0	0
2 (w=3, v=4)	0	0	0	0	0	0	0	0
3 (w=4, v=5)	0	0	0	0	0	0	0	0
4 (w=5, v=8)	0	0	0	0	0	0	0	0

Step 1 / 32 (i=1, w=0). Skipped item → carry dp[i-1][w].

0/1 Knapsack Recurrence & Complexity

Recurrence: dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]])

Base: dp[0][w] = 0. Complexity: O(nC) time, O(nC) space; can compress to O(C) space with 1D rolling (iterate w descending).

Unbounded Knapsack

1D Rolling Array

Pseudocode

1function unbounded(weights, values, W):
2  dp = array(W+1, 0)
3  for w in 0..W:
4    for i in 0..len(weights)-1:
5      if w >= weights[i]:
6        dp[w] = max(dp[w], values[i] + dp[w-weights[i]])
7  return dp[W]

Matrix Chain Multiplication

Interval DP

Pseudocode

1function matrixChain(p):
2  n = len(p) - 1
3  dp = array(n, n, 0)
4  for len_ in 2..n:
5    for i in 1..n-len_+1:
6      j = i + len_ - 1
7      dp[i][j] = +INF
8      for k in i..j-1:
9        cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]
10        dp[i][j] = min(dp[i][j], cost)
11  return dp[1][n]

Sequences & Strings

Advanced Patterns

1function knap01(weights, values, W): 2 n = len(weights) 3 dp = array(n+1, W+1, 0) 4 for i in 1..n: 5 for w in 0..W: 6 dp[i][w] = dp[i-1][w] 7 if w >= weights[i-1]: 8 dp[i][w] = max(dp[i][w], values[i-1] + dp[i-1][w-weights[i-1]]) 9 return dp[n][W]

i/w

1 (w=2, v=3)

2 (w=3, v=4)

3 (w=4, v=5)

4 (w=5, v=8)

1function unbounded(weights, values, W): 2 dp = array(W+1, 0) 3 for w in 0..W: 4 for i in 0..len(weights)-1: 5 if w >= weights[i]: 6 dp[w] = max(dp[w], values[i] + dp[w-weights[i]]) 7 return dp[W]

1function matrixChain(p): 2 n = len(p) - 1 3 dp = array(n, n, 0) 4 for len_ in 2..n: 5 for i in 1..n-len_+1: 6 j = i + len_ - 1 7 dp[i][j] = +INF 8 for k in i..j-1: 9 cost = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] 10 dp[i][j] = min(dp[i][j], cost) 11 return dp[1][n]