W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Dynamic Programming

Memoization, Tabulation, Knapsack, LCS, LIS, Grid DP, Coin Change & more.

What is Dynamic Programming?

Recursive: O(2^n) → DP: O(n)

Remembering Past Solutions

Imagine writing down 1 + 1 + 1 + 1 + 1 = 5 on a piece of paper. If you add another + 1 to the end and ask what the new total is, you don't count the ones all over again. You simply remember the previous answer was 5, add 1, and say "6".

Dynamic Programming (DP) is an optimization strategy that solves complex problems by breaking them down into simpler, overlapping subproblems and caching their results to avoid redundant calculations.

Prerequisites for Dynamic Programming:

Overlapping Subproblems: The same subproblems are solved repeatedly during recursion.
Optimal Substructure: The optimal solution to a problem can be constructed from the optimal solutions of its subproblems.

Approaches to Dynamic Programming:

Top-Down (Memoization): A recursive approach that checks a cache (memo table) before executing calculations, running only when a subproblem hasn't been solved yet.
Bottom-Up (Tabulation): An iterative approach that starts from base cases and fills a table (usually a 1D or 2D array) up to the target solution.

C++ Code — What is Dynamic Programming?

#include <iostream>
#include <vector>
using namespace std;

// 1. Top-Down with Memoization - O(n) time, O(n) space
vector<int> memo(100, -1);
int fibMemo(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // Return cached result
    
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

// 2. Bottom-Up Tabulation - O(n) time, O(n) space
int fibTabulation(int n) {
    if (n <= 1) return n;
    
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 3. Space-Optimized Tabulation - O(n) time, O(1) space
int fibOptimized(int n) {
    if (n <= 1) return n;
    
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    int n = 10;
    cout << "Fibonacci(" << n << ") memoized: " << fibMemo(n) << endl;
    cout << "Fibonacci(" << n << ") optimized: " << fibOptimized(n) << endl;
    return 0;
}

Climbing Stairs & House Robber

Time: O(n) | Space: O(1) with optimization

1D Dynamic Programming

1D DP stores solutions to subproblems along a single dimension, typically representing indices in an array.

1. Climbing Stairs

You can climb 1 or 2 steps at a time. To find the number of unique ways to reach step n:

Observation: The last step can only be reached from step n - 1 (via a 1-step leap) or step n - 2 (via a 2-step leap).
Recurrence Relation: ways(n) = ways(n - 1) + ways(n - 2). (This is the Fibonacci sequence).

2. House Robber

A robber wants to rob houses along a street but cannot rob adjacent houses due to security alarms.

Decisions at house i:
- Rob: Take house loot + max money robbed up to house i - 2.
- Skip: Take max money robbed up to house i - 1.
Recurrence Relation: dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]).

C++ Code — Climbing Stairs & House Robber

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Climbing Stairs - O(n) time, O(1) space
int climbStairs(int n) {
    if (n <= 2) return n;
    
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// House Robber - O(n) time, O(1) space
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    
    int prev2 = nums[0];
    int prev1 = max(nums[0], nums[1]);
    
    for (int i = 2; i < n; i++) {
        int curr = max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

int main() {
    cout << "Ways to climb 5 steps: " << climbStairs(5) << endl;
    vector<int> houses = {2, 7, 9, 3, 1};
    cout << "Max robbery yield: " << rob(houses) << endl;  // 12 (2 + 9 + 1)
    return 0;
}

0/1 Knapsack Problem

0/1 Knapsack: O(n*W) time, O(W) space optimized

Binary Choices Under Constraints

Imagine packing a hiking backpack of capacity W. For each item (with a given weight and value), you must make a binary choice: either pack it (adding its value but reducing the remaining capacity) or leave it behind.

In 0/1 Knapsack, items cannot be divided; you either take them or leave them.

DP Formulation:

State: Let dp[i][w] represent the maximum value using the first i items with a weight limit of w.
Decisions:
- Exclude: dp[i - 1][w].
- Include: value[i - 1] + dp[i - 1][w - weight[i - 1]] (only valid if weight fits).
Recurrence: dp[i][w] = max(dp[i - 1][w], value[i - 1] + dp[i - 1][w - weight[i - 1]])

Space Optimization:

Since the state transitions only rely on values from the previous row i - 1, we can shrink the grid into a single 1D array of size W + 1. To avoid overwriting values from the same iteration, we iterate the capacity backwards from W down to weight[i].

C++ Code — 0/1 Knapsack Problem

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 0/1 Knapsack - Space Optimized 1D DP
int knapsack1D(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // Iterate backwards to prevent multiple inclusions of the same item
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
    return dp[W];
}

// Subset Sum - Can we partition a subset to equal a target sum?
bool subsetSum(vector<int>& nums, int target) {
    vector<bool> dp(target + 1, false);
    dp[0] = true;  // Sum 0 is always possible
    
    for (int num : nums) {
        for (int s = target; s >= num; s--) {
            dp[s] = dp[s] || dp[s - num];
        }
    }
    return dp[target];
}

int main() {
    vector<int> weights = {1, 2, 3, 4};
    vector<int> values = {1, 4, 5, 7};
    int W = 5;
    cout << "Max Knapsack Value: " << knapsack1D(weights, values, W) << endl; // 9
    return 0;
}

Longest Common Subsequence (LCS)

Time: O(m*n) | Space: O(m*n), can be O(n) with optimization

String Alignments

Imagine checking two DNA strands for shared gene sequences, or comparing two code revisions to highlight changes (like git diff).

A subsequence is a sequence derived from another sequence by deleting some elements without changing the order of the remaining elements.

DP Formulation:

State: Let dp[i][j] represent the length of the LCS of strings s1[0..i-1] and s2[0..j-1].
Transitions:
- If s1[i - 1] == s2[j - 1], the characters match: dp[i][j] = 1 + dp[i - 1][j - 1]
- Otherwise, they don't match, so we check both possibilities: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

C++ Code — Longest Common Subsequence (LCS)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// Compute LCS Length
int lcsLength(string s1, string s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

// Backtrack to reconstruct the LCS String
string lcsString(string s1, string s2) {
    int m = s1.length(), n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    string lcs = "";
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (s1[i - 1] == s2[j - 1]) {
            lcs = s1[i - 1] + lcs;
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}

int main() {
    string s1 = "ABCDGH", s2 = "AEDFHR";
    cout << "LCS Length: " << lcsLength(s1, s2) << endl; // 3
    cout << "LCS String: " << lcsString(s1, s2) << endl; // "ADH"
    return 0;
}

Longest Increasing Subsequence (LIS)

DP: O(n²) | Binary Search: O(n log n)

Chain of Increasing Elements

Imagine stacking boxes of varying sizes. You can only stack a box on top of another if it is strictly larger in size. You want to build the tallest stack possible.

The Longest Increasing Subsequence problem asks you to find the length of the longest subsequence in an array such that all elements are sorted in strictly increasing order.

1. Standard DP Approach (`O(n²)`):

Let dp[i] be the length of the LIS ending at index i. For every element, we check all preceding elements j < i. If nums[j] < nums[i], then dp[i] = max(dp[i], dp[j] + 1).

2. Patience Sorting Binary Search (`O(n log n)`):

We maintain a dynamic active list representing the smallest ending element for all increasing subsequences found so far. For each element in the input:

Use binary search to find its insertion position in our active list.
If the element is larger than all elements in the list, append it (extending the maximum length).
Otherwise, overwrite the first element in the list that is greater than or equal to it (updating the boundary value).

C++ Code — Longest Increasing Subsequence (LIS)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// LIS O(n²) DP solution
int lisDP(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    vector<int> dp(n, 1);
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

// LIS O(n log n) Binary Search solution
int lisBinarySearch(vector<int>& nums) {
    vector<int> tail;
    
    for (int num : nums) {
        auto it = lower_bound(tail.begin(), tail.end(), num);
        if (it == tail.end()) {
            tail.push_back(num); // Extend LIS
        } else {
            *it = num; // Maintain smaller bounds
        }
    }
    return tail.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "LIS Length (n log n): " << lisBinarySearch(nums) << endl; // 4
    return 0;
}

Grid DP - Unique Paths & Min Cost

Time: O(m*n) | Space: O(n) with optimization

2D Coordinate Traversals

Imagine a delivery drone navigating a city street grid from the top-left corner (0,0) to the bottom-right corner (m-1, n-1). The drone is programmed to only travel East (Right) or South (Down) to conserve battery.

In Grid DP, states are mapped to cell coordinates (i, j).

1. Unique Paths (Counting Configuration)

Recurrence: The drone can reach cell (i, j) from either the cell directly above (i-1, j) or the cell to its left (i, j-1).
Formula: dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. Minimum Path Sum (Optimization Configuration)

Formula: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

C++ Code — Grid DP - Unique Paths & Min Cost

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Unique Paths - Space optimized O(n)
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1);
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}

// Minimum Path Sum - O(m * n) time
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n));
    
    dp[0][0] = grid[0][0];
    
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];
    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

int main() {
    cout << "Unique Paths (3x7): " << uniquePaths(3, 7) << endl; // 28
    vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    cout << "Min Path Sum: " << minPathSum(grid) << endl; // 7
    return 0;
}

Coin Change Problem

Time: O(amount * coins) | Space: O(amount)

Making Change Combinations

Imagine making change at a cash register. You have a roll of coins of various values (e.g., quarters, dimes, nickels) and want to find the most efficient way to make a target amount.

This is an Unbounded Knapsack problem: you can reuse coins of the same value as many times as needed.

1. Minimum Coins (Optimization)

State: Let dp[amount] be the minimum number of coins needed to make change.
Recurrence: For each coin denomination, if coin <= i, then dp[i] = min(dp[i], 1 + dp[i - coin]).

2. Number of Ways (Counting)

State: Let dp[amount] be the number of unique combinations that sum to the target amount.
Recurrence: For each coin denomination, loop through amounts from coin to target: dp[i] += dp[i - coin].

C++ Code — Coin Change Problem

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Coin Change 1: Minimum coins
int minCoins(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

// Coin Change 2: Total combinations
int countWays(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 0);
    dp[0] = 1;
    
    for (int coin : coins) {
        for (int i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 11;
    cout << "Min coins for 11: " << minCoins(coins, amount) << endl; // 3 (5 + 5 + 1)
    cout << "Unique ways to make 11: " << countWays(coins, amount) << endl; // 11
    return 0;
}

#include <iostream> #include <vector> using namespace std; // 1. Top-Down with Memoization - O(n) time, O(n) space vector<int> memo(100, -1); int fibMemo(int n) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; // Return cached result memo[n] = fibMemo(n - 1) + fibMemo(n - 2); return memo[n]; } // 2. Bottom-Up Tabulation - O(n) time, O(n) space int fibTabulation(int n) { if (n <= 1) return n; vector<int> dp(n + 1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } // 3. Space-Optimized Tabulation - O(n) time, O(1) space int fibOptimized(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } int main() { int n = 10; cout << "Fibonacci(" << n << ") memoized: " << fibMemo(n) << endl; cout << "Fibonacci(" << n << ") optimized: " << fibOptimized(n) << endl; return 0; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; // Climbing Stairs - O(n) time, O(1) space int climbStairs(int n) { if (n <= 2) return n; int prev2 = 1, prev1 = 2; for (int i = 3; i <= n; i++) { int curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; } // House Robber - O(n) time, O(1) space int rob(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; if (n == 1) return nums[0]; int prev2 = nums[0]; int prev1 = max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int curr = max(prev1, prev2 + nums[i]); prev2 = prev1; prev1 = curr; } return prev1; } int main() { cout << "Ways to climb 5 steps: " << climbStairs(5) << endl; vector<int> houses = {2, 7, 9, 3, 1}; cout << "Max robbery yield: " << rob(houses) << endl; // 12 (2 + 9 + 1) return 0; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; // 0/1 Knapsack - Space Optimized 1D DP int knapsack1D(vector<int>& weights, vector<int>& values, int W) { int n = weights.size(); vector<int> dp(W + 1, 0); for (int i = 0; i < n; i++) { // Iterate backwards to prevent multiple inclusions of the same item for (int w = W; w >= weights[i]; w--) { dp[w] = max(dp[w], values[i] + dp[w - weights[i]]); } } return dp[W]; } // Subset Sum - Can we partition a subset to equal a target sum? bool subsetSum(vector<int>& nums, int target) { vector<bool> dp(target + 1, false); dp[0] = true; // Sum 0 is always possible for (int num : nums) { for (int s = target; s >= num; s--) { dp[s] = dp[s] || dp[s - num]; } } return dp[target]; } int main() { vector<int> weights = {1, 2, 3, 4}; vector<int> values = {1, 4, 5, 7}; int W = 5; cout << "Max Knapsack Value: " << knapsack1D(weights, values, W) << endl; // 9 return 0; }

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; // Compute LCS Length int lcsLength(string s1, string s2) { int m = s1.length(), n = s2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n]; } // Backtrack to reconstruct the LCS String string lcsString(string s1, string s2) { int m = s1.length(), n = s2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } string lcs = ""; int i = m, j = n; while (i > 0 && j > 0) { if (s1[i - 1] == s2[j - 1]) { lcs = s1[i - 1] + lcs; i--; j--; } else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } return lcs; } int main() { string s1 = "ABCDGH", s2 = "AEDFHR"; cout << "LCS Length: " << lcsLength(s1, s2) << endl; // 3 cout << "LCS String: " << lcsString(s1, s2) << endl; // "ADH" return 0; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; // LIS O(n²) DP solution int lisDP(vector<int>& nums) { int n = nums.size(); if (n == 0) return 0; vector<int> dp(n, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen; } // LIS O(n log n) Binary Search solution int lisBinarySearch(vector<int>& nums) { vector<int> tail; for (int num : nums) { auto it = lower_bound(tail.begin(), tail.end(), num); if (it == tail.end()) { tail.push_back(num); // Extend LIS } else { *it = num; // Maintain smaller bounds } } return tail.size(); } int main() { vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18}; cout << "LIS Length (n log n): " << lisBinarySearch(nums) << endl; // 4 return 0; }

#include <iostream> #include <vector> #include <algorithm> using namespace std; // Unique Paths - Space optimized O(n) int uniquePaths(int m, int n) { vector<int> dp(n, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } // Minimum Path Sum - O(m * n) time int minPathSum(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> dp(m, vector<int>(n)); dp[0][0] = grid[0][0]; for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j]; for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]); } } return dp[m - 1][n - 1]; } int main() { cout << "Unique Paths (3x7): " << uniquePaths(3, 7) << endl; // 28 vector<vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}; cout << "Min Path Sum: " << minPathSum(grid) << endl; // 7 return 0; }

#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; // Coin Change 1: Minimum coins int minCoins(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i && dp[i - coin] != INT_MAX) { dp[i] = min(dp[i], 1 + dp[i - coin]); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; } // Coin Change 2: Total combinations int countWays(vector<int>& coins, int amount) { vector<int> dp(amount + 1, 0); dp[0] = 1; for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } int main() { vector<int> coins = {1, 2, 5}; int amount = 11; cout << "Min coins for 11: " << minCoins(coins, amount) << endl; // 3 (5 + 5 + 1) cout << "Unique ways to make 11: " << countWays(coins, amount) << endl; // 11 return 0; }

Dynamic Programming

What is Dynamic Programming?

Remembering Past Solutions

Prerequisites for Dynamic Programming:

Approaches to Dynamic Programming:

Climbing Stairs & House Robber

1D Dynamic Programming

1. Climbing Stairs

2. House Robber

0/1 Knapsack Problem

Binary Choices Under Constraints

DP Formulation:

Space Optimization:

Longest Common Subsequence (LCS)

String Alignments

DP Formulation:

Longest Increasing Subsequence (LIS)

Chain of Increasing Elements

1. Standard DP Approach (O(n²)):

2. Patience Sorting Binary Search (O(n log n)):

Grid DP - Unique Paths & Min Cost

2D Coordinate Traversals

1. Unique Paths (Counting Configuration)

2. Minimum Path Sum (Optimization Configuration)

Coin Change Problem

Making Change Combinations

1. Minimum Coins (Optimization)

2. Number of Ways (Counting)

Dynamic Programming

What is Dynamic Programming?

Remembering Past Solutions

Prerequisites for Dynamic Programming:

Approaches to Dynamic Programming:

Climbing Stairs & House Robber

1D Dynamic Programming

1. Climbing Stairs

2. House Robber

0/1 Knapsack Problem

Binary Choices Under Constraints

DP Formulation:

Space Optimization:

Longest Common Subsequence (LCS)

String Alignments

DP Formulation:

Longest Increasing Subsequence (LIS)

Chain of Increasing Elements

1. Standard DP Approach (O(n²)):

2. Patience Sorting Binary Search (O(n log n)):

Grid DP - Unique Paths & Min Cost

2D Coordinate Traversals

1. Unique Paths (Counting Configuration)

2. Minimum Path Sum (Optimization Configuration)

Coin Change Problem

Making Change Combinations

1. Minimum Coins (Optimization)

2. Number of Ways (Counting)

1. Standard DP Approach (`O(n²)`):

2. Patience Sorting Binary Search (`O(n log n)`):

1. Standard DP Approach (`O(n²)`):

2. Patience Sorting Binary Search (`O(n log n)`):