</>
Loading
Loading
Breaking Down Complex Problems
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when subproblems overlap and have optimal substructure.
Dynamic Programming works when a problem has overlapping subproblems and optimal substructure. The key is to store solutions to subproblems to avoid redundant calculations.
// Fibonacci - Memoization (Top-Down)
function fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
// Fibonacci - Tabulation (Bottom-Up)
function fibTab(n) {
if (n <= 1) return n;
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Fibonacci - Space Optimized
function fibOptimized(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}The same subproblems are solved multiple times
The optimal solution contains optimal solutions to subproblems
Define what information uniquely identifies a subproblem
Choose or skip each item to maximize value within capacity
Find the longest subsequence satisfying certain conditions
Practice more DP problems on LeetCode. Focus on understanding the recurrence relation before coding.