Dynamic Programming LeetCode Problems: 10 Solved in JS

Dynamic programming has a reputation for being the hardest interview topic, but most DP problems follow the same few steps. Once you see them, LeetCode questions that looked unrelated start to look familiar. This tutorial walks through what DP really is, a five-step recipe, and ten classic LeetCode problems from easy to hard, all in JavaScript. For each one you get the state, the recurrence, and a bottom-up solution, with the brute-force and memoized versions where they teach something. Every solution in the video is run in Node 22 against LeetCode’s official examples.

⚡ TL;DR – DP fits when a problem has overlapping subproblems and optimal substructure. – Recipe: define the state, write the recurrence, set base cases, choose memoization or tabulation, then optimize space. – Plain recursive Fibonacci makes more than 2.5 million calls for fib(30). The memoized version makes 59. – Patterns covered: 1D DP, unbounded knapsack, 0/1 knapsack (loop backwards), grid DP, LIS-style “look back”, and two-string 2D tables. – Always write brute force first. It tells you the state and the recurrence.

Before you start

• Comfortable with JavaScript functions, arrays, Map and recursion.
• Node.js to run the snippets (node file.js).
• A LeetCode account if you want to submit; the problem numbers are listed below.

What DP actually is

Start with Fibonacci. The plain recursive version is correct, but fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. The same small problems are solved over and over. That’s overlapping subproblems. The fix is to remember every answer:

const memo = new Map();
function fib(n) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const v = fib(n - 1) + fib(n - 2);
  memo.set(n, v);
  return v;
}

The second ingredient is optimal substructure: the best answer to the big problem is built from best answers to smaller ones. In interviews, watch for phrasing like “count the number of ways”, “minimum or maximum”, “longest”, or “is it possible”.

The five-step recipe

1. State: what does dp[i] (or dp[i][j]) mean, in words?
2. Recurrence: how is a state computed from smaller states?
3. Base cases: the smallest states you know directly.
4. Order: top-down memoization (recursion plus cache) or bottom-up tabulation (loops filling a table).
5. Space: keep only the rows or values the recurrence actually reads.

Step 1: Climbing Stairs (LeetCode 70), 1D DP

You can climb 1 or 2 steps. How many distinct ways to reach step n? The last move was either from n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2). It’s Fibonacci in disguise.

function climbStairs(n) {
  let a = 1, b = 1;                 // ways(0), ways(1)
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

Space optimization in action: you only ever read the last two values.

Step 2: House Robber (LeetCode 198)

You can’t rob two adjacent houses. At each house, either skip it (keep the best so far) or rob it (its value plus the best up to two houses back):

function rob(nums) {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) [prev2, prev1] = [prev1, Math.max(prev1, prev2 + x)];
  return prev1;
}

Step 3: Coin Change (LeetCode 322), unbounded knapsack

Fewest coins to make amount, with unlimited coins of each kind. dp[a] is the fewest coins for amount a:

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
  return dp[amount] === Infinity ? -1 : dp[amount];
}

Use Infinity for “impossible” so Math.min-style comparisons work, and convert to -1 only at the end.

Step 4: Longest Increasing Subsequence (LeetCode 300)

dp[i] is the length of the longest increasing subsequence ending at i. Look back at every earlier j with a smaller value:

function lengthOfLIS(nums) {
  const dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++)
    for (let j = 0; j < i; j++)
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  return Math.max(...dp);
}

The answer is the maximum over all positions, not dp[n-1], a common bug. This is O(n²); a patience-sorting version with binary search is O(n log n) if you need it.

Step 5: Longest Common Subsequence (LeetCode 1143), two strings

Two strings almost always means a 2D table. dp[i][j] is the LCS of the first i chars of a and the first j of b:

function longestCommonSubsequence(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0));
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1] + 1
        : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[a.length][b.length];
}

The extra row and column for the empty prefix remove all the edge-case ifs.

Step 6: Unique Paths (LeetCode 62), grid DP

Moving only down or right, the paths into a cell are paths from above plus paths from the left:

function uniquePaths(m, n) {
  const row = new Array(n).fill(1);
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++) row[j] += row[j - 1];
  return row[n - 1];
}

One row is enough: before the update, row[j] still holds “above”, and row[j-1] already holds “left”.

Step 7: Minimum Path Sum (LeetCode 64)

Same movement, but minimize cost: dp[i][j] = grid[i][j] + min(above, left), with the first row and column only reachable one way.

function minPathSum(grid) {
  const n = grid[0].length, dp = new Array(n).fill(Infinity);
  dp[0] = 0;
  for (const row of grid)
    for (let j = 0; j < n; j++)
      dp[j] = row[j] + Math.min(dp[j], j > 0 ? dp[j - 1] : Infinity);
  return dp[n - 1];
}

Step 8: Partition Equal Subset Sum (LeetCode 416), 0/1 knapsack

Can the array split into two equal-sum halves? Equivalent: can some subset reach total / 2? Each number is used at most once, so loop the target backwards:

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;
  const target = total / 2, dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums)
    for (let s = target; s >= x; s--) dp[s] ||= dp[s - x];
  return dp[target];
}

Looping forwards would let the same number be reused, turning it into unbounded knapsack and producing wrong trues. This single detail is the most common DP interview bug.

Step 9: Edit Distance (LeetCode 72)

Minimum inserts, deletes and replaces to turn a into b. Same two-pointer state as LCS. If the characters match, copy the diagonal; otherwise take one plus the minimum of delete (above), insert (left) and replace (diagonal). Row 0 and column 0 count up, because turning an empty string into j characters takes j inserts.

function minDistance(a, b) {
  const dp = Array.from({ length: a.length + 1 }, (_, i) =>
    Array.from({ length: b.length + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0)));
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i - 1] === b[j - 1]
        ? dp[i - 1][j - 1]
        : 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
  return dp[a.length][b.length];
}
// minDistance("horse", "ros") === 3; minDistance("intention", "execution") === 5

Step 10: Word Break (LeetCode 139)

Can s be split into dictionary words (reuse allowed)? dp[i] is true if the first i characters can be split. dp[0] is true. For each i, look for a split point j where dp[j] is true and s.slice(j, i) is a word:

function wordBreak(s, wordDict) {
  const words = new Set(wordDict), dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++)
    for (let j = 0; j < i && !dp[i]; j++)
      if (dp[j] && words.has(s.slice(j, i))) dp[i] = true;
  return dp[s.length];
}
// "leetcode" -> true (dp[4] via "leet", dp[8] via "code"); "catsandog" -> false

A Set keeps the lookup fast. This is the template for many string-partition problems.

Pattern cheat sheet

Troubleshooting common DP bugs

• Off-by-one in 2D tables: size them (m+1) x (n+1) and index strings with i-1, j-1.
• Wrong answer location: LIS takes the max over all dp[i]; most others read the last cell.
• Reusing items in 0/1 knapsack: loop the capacity backwards.
• Stack overflow in memoized recursion: Node’s default stack can’t handle very deep recursion; switch to tabulation.
• Infinity leaking into output: map “impossible” to the problem’s sentinel (-1, false) at the end.

FAQ

Memoization or tabulation in interviews?

Start with memoization: it falls straight out of the brute force. Convert to tabulation if asked about stack depth or space.

How do I find the state?

Ask what changes between recursive calls in the brute force. Those parameters are the state.

How many problems should I practise?

These ten cover the patterns that come up most. Solve each without looking, then try variations (House Robber II, Coin Change II, Longest Palindromic Subsequence).

Problem links

70 · 198 · 322 · 300 · 1143 · 62 · 64 · 416 · 72 · 139

Key takeaways

• Brute force first, then memo, then table, then trim space.
• Define the state in words before writing code.
• Recognize the six patterns and most problems become variations.
• Loop direction is what separates 0/1 knapsack from unbounded knapsack.