# Explain Dynamic Programming and Other Techniques with Examples In this article, we will dive into the world of **dynamic programming (DP)** and related optimization techniques, focusing on solving some programming challenges step by step. We’ll break down each problem, present multiple solutions in JavaScript, and explain the time and space complexities. These problems remain **high-value interview questions in 2025**, commonly appearing on platforms like LeetCode, HackerRank, and coding assessments. --- ## 2. Longest Increasing Subsequence (LIS) ### 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 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 ```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)) --- ## 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) ```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) Optimal solution for interviews. ```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); } ``` --- ## 5. 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. --- ## 6. 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; } ``` --- ## 7. 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 **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 ```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). - Still a **tough interview classic in 2025**. --- ## 9. 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) --- ## 10. 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) --- ## 11. 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) --- # Conclusion Dynamic programming and related techniques (binary search, stack-based optimizations, memoization) are **essential interview skills in 2025**. 🚀

#dynamic-programming

اشرح البرمجة الديناميكية وتقنيات أخرى مع أمثلة