Dynamic Programming: TypeScript in Practice from Climbing Stairs to the Knapsack Problem

Table of Contents

Overview Problem Definition Core Principle: Step-by-Step Illustration Detailed Algorithm Steps TypeScript Implementation 1. Stair Climbing 2. House Robber 3. Longest Common Subsequence 4. Edit Distance 5. 0-1 Knapsack 6. Longest Increasing Subsequence Engineering Optimization: State Compression and Iteration Order Applications and Limitations Typical Applications Limitations Summary

921 words

5 minutes

Dynamic Programming: TypeScript in Practice from Climbing Stairs to the Knapsack Problem

2026-04-26

Algorithms

Dynamic Programming

/

TypeScript

/

Algorithms

Overview#

Dynamic Programming (DP) avoids repeated computation by storing the results of subproblems. It is suitable for scenarios with optimal substructure and overlapping subproblems, such as path counting, sequence matching, knapsack selection, and interval optimal values.

Prerequisites

Recursion / Memoized Search: Understanding state dependencies from a top-down perspective

Arrays and Matrices: One-dimensional and two-dimensional DP tables are the most common state storage

State Transitions: Deriving the current problem from known smaller problems

Problem Definition#

Given an optimization or counting problem that can be decomposed into overlapping subproblems, define the state and solve for the final answer through a transition equation.

Element	Description
Input	Sequence, capacity, target value, or two strings
Output	Maximum/minimum value, number of solutions, longest length, or minimum number of operations
Core State	`dp[i]`, `dp[i][j]`, or a compressed one-dimensional array
Key Questions	State meaning, transition equation, initialization, iteration order

Core Principle: Step-by-Step Illustration#

Taking stair climbing as an example, reaching step i can only come from i - 1 or i - 2:

The state transition is:

1
dp[i] = dp[i - 1] + dp[i - 2]

The difficulty of dynamic programming usually lies not in the code, but in reformulating the problem as “how the current state can be obtained from smaller states.”

Detailed Algorithm Steps#

1
Algorithm: SolveDP(problem)
2
Input: A decomposable problem
3
Output: Optimal value, number of solutions, or feasibility
4

5
1. Define the state: what dp[i] or dp[i][j] represents
6
2. Write the transition equation: which previous states the current state comes from
7
3. Initialize boundary states: empty array, first row, first column, etc.
8
4. Determine the traversal order: ensure dependent states have already been computed
9
5. Return the answer: dp[n], dp[m][n], or the maximum value in the table

Complexity Analysis:

Problem	State Definition	Time Complexity	Space Complexity
Stair Climbing	`dp[i]` number of ways to reach step i	O(n)	O(1)
House Robber	`dp[i]` maximum profit from first i houses	O(n)	O(1)
LCS	`dp[i][j]` longest common subsequence of two prefixes	O(mn)	O(mn)
Edit Distance	`dp[i][j]` minimum operations to convert prefixes	O(mn)	O(mn)
0-1 Knapsack	`dp[w]` maximum value at capacity w	O(nW)	O(W)

TypeScript Implementation#

1. Stair Climbing#

1
function climbStairs(n: number): number {
2
  if (n <= 2) return n;
3

4
  let prev2 = 1;
5
  let prev1 = 2;
6

7
  for (let i = 3; i <= n; i++) {
8
    const current = prev1 + prev2;
9
    prev2 = prev1;
10
    prev1 = current;
11
  }
12

13
  return prev1;
14
}

2. House Robber#

1
function rob(nums: number[]): number {
2
  let prev2 = 0;
3
  let prev1 = 0;
4

5
  for (const money of nums) {
6
    const current = Math.max(prev1, prev2 + money);
7
    prev2 = prev1;
8
    prev1 = current;
9
  }
10

11
  return prev1;
12
}

3. Longest Common Subsequence#

1
function longestCommonSubsequence(text1: string, text2: string): number {
2
  const m = text1.length;
3
  const n = text2.length;
4
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
5

6
  for (let i = 1; i <= m; i++) {
7
    for (let j = 1; j <= n; j++) {
8
      if (text1[i - 1] === text2[j - 1]) {
9
        dp[i][j] = dp[i - 1][j - 1] + 1;
10
      } else {
11
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
12
      }
13
    }
14
  }
15

16
  return dp[m][n];
17
}

4. Edit Distance#

1
function minDistance(word1: string, word2: string): number {
2
  const m = word1.length;
3
  const n = word2.length;
4
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
5

6
  for (let i = 0; i <= m; i++) dp[i][0] = i;
7
  for (let j = 0; j <= n; j++) dp[0][j] = j;
8

9
  for (let i = 1; i <= m; i++) {
10
    for (let j = 1; j <= n; j++) {
11
      if (word1[i - 1] === word2[j - 1]) {
12
        dp[i][j] = dp[i - 1][j - 1];
13
      } else {
14
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
15
      }
16
    }
17
  }
18

19
  return dp[m][n];
20
}

5. 0-1 Knapsack#

1
function knapsack(weights: number[], values: number[], capacity: number): number {
2
  const dp = new Array(capacity + 1).fill(0);
3

4
  for (let i = 0; i < weights.length; i++) {
5
    for (let w = capacity; w >= weights[i]; w--) {
6
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
7
    }
8
  }
9

10
  return dp[capacity];
11
}

6. Longest Increasing Subsequence#

1
function lengthOfLIS(nums: number[]): number {
2
  const tails: number[] = [];
3

4
  for (const num of nums) {
5
    let left = 0;
6
    let right = tails.length;
7

8
    while (left < right) {
9
      const mid = left + Math.floor((right - left) / 2);
10
      if (tails[mid] < num) left = mid + 1;
11
      else right = mid;
12
    }
13

14
    tails[left] = num;
15
  }
16

17
  return tails.length;
18
}

Engineering Optimization: State Compression and Iteration Order#

Optimization	Approach	Notes
One-dimensional compression	Keep only the previous row or necessary states	Must confirm dependency direction
Rolling variables	E.g., stair climbing keeps only two values	Suitable when depending on a fixed number of old states
0-1 Knapsack	Iterate capacity in reverse order	Prevents the same item from being used repeatedly
Unbounded Knapsack	Iterate capacity in forward order	Allows the same item to be used repeatedly
Memoized Search	Cache results top-down	Closer to the recursive definition, intuitive for debugging

DP optimization cannot focus solely on space reduction; it must also ensure that state dependencies are not overwritten prematurely.

Applications and Limitations#

Typical Applications#

Path counting, stair climbing, grid paths
Sequence problems: LCS, LIS, edit distance
Knapsack and resource allocation
Stock trading, interval DP, bitmask DP

Limitations#

Limitation	Description
Difficult state design	Unclear state meaning leads to incorrect transitions
Space can be large	Two-dimensional or multi-dimensional DP easily consumes large amounts of memory
Not suitable without overlapping subproblems	DP yields limited benefit when there is no repeated computation

Summary#

Key Takeaways:

DP solves problems with overlapping subproblems and optimal substructure.
Before writing DP, first clarify the meaning of each position in the dp array.
The iteration order must ensure that dependency states have already been computed.
The core of state compression is ensuring that old states are not incorrectly overwritten.