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 in 2025, commonly appearing on platforms like LeetCode, HackerRank, and company assessments.

---

2. 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)

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)

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 in 2025 for LIS.

---

3. 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

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

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))

---

4. 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)

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)

Optimal solution for interviews.

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);
}

---

5. Longest Palindromic Subsequence

Problem Description

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

O(n²) DP Solution

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.

---

6. Maximum Product Subarray

Problem Description

Find the contiguous subarray with the maximum product.

O(n), O(1) Solution

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;
}

---

7. Largest Rectangle in a Histogram

Problem Description

Find the largest rectangle area in a histogram.

Stack-Based O(n) Solution

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 optimal solution in 2025.

---

8. 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

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).
• Still a tough interview classic in 2025.

---

9. Counting Bits

Problem Description

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

O(n) Solution

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)

---

10. Perfect Squares

Problem Description

Find the least number of perfect square numbers that sum to n.

DP Solution

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)

---

11. Unique Paths

Problem Description

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

DP Solution

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)

---

Conclusion

Dynamic programming and related techniques (binary search optimization, stack-based algorithms, memoization) are essential coding interview skills in 2025. 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.