---
title: Explain Dynamic Programming and Other Techniques with Examples
description: 'Dynamic programming in JavaScript: memoization, tabulation, state design — walked through classic LeetCode problems with runnable JS code.'
url: https://nerdleveltech.com/dynamic-programming-js-2025
language: en
date: '2023-06-11'
updated: '2026-05-05'
category: performance
tags:
  - JavaScript
  - Dynamic Programming
  - Algorithms
  - Coding Interview
markdown_url: https://nerdleveltech.com/dynamic-programming-js-2025.md
attribution: 'Source: NerdLevelTech — https://nerdleveltech.com/dynamic-programming-js-2025'
terms: https://nerdleveltech.com/llms.txt
---

# Explain Dynamic Programming and Other Techniques with Examples

In this comprehensive **dynamic programming tutorial**, we dive into **DP algorithms** and optimization techniques, solving classic **coding interview problems** step by step. Whether you're preparing for **FAANG interviews** or improving your **data structures and algorithms** skills, these patterns are essential.

We'll break down each problem with multiple **JavaScript solutions**, explain **time and space complexity**, and show you optimized approaches used in **technical interviews** at Google, Meta, Amazon, and Microsoft.

These **LeetCode problems** remain high-value coding interview questions, commonly appearing on platforms like LeetCode, HackerRank, and company assessments.

---

## 1. Longest Increasing Subsequence (LIS)

The **Longest Increasing Subsequence** is a classic **DP problem** frequently asked in **coding interviews**. It tests your understanding of **memoization** and **binary search optimization**.

### Problem Description
Find the length of the longest subsequence of a given sequence, such that all elements are sorted in increasing order.

Example: `[10, 9, 2, 5, 3, 7, 101, 18]` → LIS is `[2, 3, 7, 101]`, length = 4.

### O(n²) DP Solution (Classic)
```js
function longestIncreasingSubsequence(nums) {
  const n = nums.length;
  if (n === 0) return 0;
  const dp = Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}
```

- **Time complexity:** O(n²)  
- **Space complexity:** O(n)  

### Optimized O(n log n) Solution (Binary Search)
```js
function longestIncreasingSubsequence(nums) {
  const tails = [];
  for (let num of nums) {
    let l = 0, r = tails.length;
    while (l < r) {
      const mid = Math.floor((l + r) / 2);
      if (tails[mid] < num) l = mid + 1;
      else r = mid;
    }
    tails[l] = num;
  }
  return tails.length;
}
```

- **Time complexity:** O(n log n)  
- **Space complexity:** O(n)  

This optimized solution is the standard approach for LIS when an O(n log n) bound is required.

---

## 2. Longest Common Subsequence (LCS)

### Problem Description
Find the longest subsequence common to two strings.  

Example: `"ABCD"` and `"ACDF"` → LCS is `"ACD"`.

### O(m × n) DP Solution
```js
function longestCommonSubsequence(str1, str2) {
  const m = str1.length, n = str2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}
```

- **Time complexity:** O(m × n)  
- **Space complexity:** O(m × n)  

### Space-Optimized O(min(m, n)) Version
```js
function longestCommonSubsequence(str1, str2) {
  if (str1.length < str2.length) [str1, str2] = [str2, str1];
  const m = str1.length, n = str2.length;
  const dp = Array.from({ length: 2 }, () => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i % 2][j] = 1 + dp[(i - 1) % 2][j - 1];
      } else {
        dp[i % 2][j] = Math.max(dp[(i - 1) % 2][j], dp[i % 2][j - 1]);
      }
    }
  }
  return dp[m % 2][n];
}
```

- **Time complexity:** O(m × n)  
- **Space complexity:** O(min(m, n))  

---

## 3. Longest Palindromic Substring

### Problem Description
Find the longest contiguous substring of a string that is a palindrome.  

Example: `"babad"` → `"bab"` or `"aba"`.

### Expand Around Center (O(n²), O(1) space)
```js
function expandAroundCenter(s, left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  return right - left - 1;
}

function longestPalindromicSubstring(s) {
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    const len = Math.max(
      expandAroundCenter(s, i, i),
      expandAroundCenter(s, i, i + 1)
    );
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
}
```

### Manacher's Algorithm (O(n), O(n) space)
A linear-time approach worth knowing for harder interview rounds, though the simpler expand-around-center solution above is usually sufficient.

```js
function manachersAlgorithm(s) {
  let T = "#" + s.split("").join("#") + "#";
  const P = Array(T.length).fill(0);
  let C = 0, R = 0, maxLen = 0, centerIndex = 0;

  for (let i = 1; i < T.length - 1; i++) {
    if (i < R) P[i] = Math.min(R - i, P[2 * C - i]);
    while (T[i + P[i] + 1] === T[i - P[i] - 1]) P[i]++;
    if (i + P[i] > R) [C, R] = [i, i + P[i]];
    if (P[i] > maxLen) [maxLen, centerIndex] = [P[i], i];
  }

  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}
```

---

## 4. Longest Palindromic Subsequence

### Problem Description
Find the longest subsequence (not substring) that is a palindrome.  

### O(n²) DP Solution
```js
function longestPalindromicSubsequence(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => Array(n).fill(0));

  for (let i = 0; i < n; i++) dp[i][i] = 1;

  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        dp[i][j] = dp[i + 1][j - 1] + 2;
      } else {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[0][n - 1];
}
```

- **Time complexity:** O(n²)  
- **Space complexity:** O(n²), reducible to O(n) with rolling arrays.  

---

## 5. Maximum Product Subarray

### Problem Description
Find the contiguous subarray with the maximum product.  

### O(n), O(1) Solution
```js
function maxProductSubarray(nums) {
  let maxProd = nums[0], minProd = nums[0], result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    const curr = nums[i];
    const temp = maxProd;
    maxProd = Math.max(curr, curr * maxProd, curr * minProd);
    minProd = Math.min(curr, curr * temp, curr * minProd);
    result = Math.max(result, maxProd);
  }

  return result;
}
```

---

## 6. Largest Rectangle in a Histogram

### Problem Description
Find the largest rectangle area in a histogram.  

### Stack-Based O(n) Solution
```js
function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length && h < heights[stack.at(-1)]) {
      const height = heights[stack.pop()];
      const width = stack.length === 0 ? i : i - stack.at(-1) - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}
```

- **Time complexity:** O(n)  
- **Space complexity:** O(n)  

This remains the textbook optimal solution and is what most interviewers expect.

---

## 7. Egg Dropping Problem

### Problem Description
Given `n` eggs and `k` floors, find the minimum number of attempts needed to find the highest floor an egg can be dropped without breaking.  

### DP Solution
```js
function eggDrop(n, k) {
  const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    dp[i][1] = 1;
    dp[i][0] = 0;
  }
  for (let j = 1; j <= k; j++) dp[1][j] = j;

  for (let i = 2; i <= n; i++) {
    for (let j = 2; j <= k; j++) {
      dp[i][j] = Infinity;
      for (let x = 1; x <= j; x++) {
        const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
        dp[i][j] = Math.min(dp[i][j], res);
      }
    }
  }
  return dp[n][k];
}
```

- **Time complexity:** O(n × k²) → can be optimized to O(n × k log k) with binary search inside the inner loop, or O(n × k) by exploiting the monotonicity of the optimal split.
- Still a tough interview classic.

---

## 8. Counting Bits

### Problem Description
Given a number `num`, return an array of the count of `1`s in binary for every number ≤ num.  

### O(n) Solution
```js
function countBits(num) {
  const dp = new Array(num + 1).fill(0);
  for (let i = 1; i <= num; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
  }
  return dp;
}
```

- **Time complexity:** O(n)  
- **Space complexity:** O(n)  

---

## 9. Perfect Squares

### Problem Description
Find the least number of perfect square numbers that sum to `n`.  

### DP Solution
```js
function numSquares(n) {
  const dp = Array(n + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
    }
  }
  return dp[n];
}
```

- **Time complexity:** O(n√n)  
- **Space complexity:** O(n)  

---

## 10. Unique Paths

### Problem Description
Find the number of unique paths in an m × n grid, moving only down or right.  

### DP Solution
```js
function uniquePaths(m, n) {
  const dp = Array(m).fill().map(() => Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}
```

- **Time complexity:** O(m × n)
- **Space complexity:** O(m × n), reducible to O(min(m, n)) with a single rolling row, or O(1) using the closed-form C(m + n − 2, m − 1) binomial coefficient.

---

## Conclusion

**Dynamic programming** and related techniques (binary search optimization, stack-based algorithms, memoization) remain core coding interview skills. These **algorithm patterns** appear consistently in **technical interviews** at top tech companies.

Key takeaways for mastering **DP problems**:
- Identify **overlapping subproblems** and **optimal substructure**
- Start with the **brute force recursive solution**, then optimize with **memoization** or **tabulation**
- Practice problems on **LeetCode**, **HackerRank**, and **NeetCode** to build pattern recognition
- Focus on **time and space complexity analysis** to explain trade-offs in interviews

Whether you're preparing for **software engineering interviews** or building **high-performance JavaScript applications**, these **algorithmic techniques** form the foundation of efficient problem-solving.