Dynamic Programming

// Climbing Stairs (LC 70) — number of ways to reach step n
// dp[i] = ways to reach step i = dp[i-1] + dp[i-2]
// Time: O(n)  Space: O(1) after optimisation
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;
}
// Space optimised: only keep the last two values (rolling variables).
// General pattern: whenever dp[i] depends only on dp[i-1] and dp[i-2],
// you can reduce O(n) space to O(1).

// LeetCode 322 — Coin Change
// Minimum number of coins to make amount. Unlimited supply per denomination.
// Time: O(amount * n)  Space: O(amount)
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1); // INF = amount+1 (impossible sentinel)
    dp[0] = 0;                          // base case: 0 coins for amount 0
    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (c <= i)
                dp[i] = min(dp[i], dp[i-c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
// Why amount+1 as INF? Any valid answer is <= amount (using all 1-coins).
// If dp[amount] > amount after filling, no solution exists.

// LeetCode 300 — Longest Increasing Subsequence
// Time: O(n^2)  Space: O(n)   [O(n log n) with patience sorting]
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);  // dp[i] = LIS ending at index i
    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])           // nums[i] extends LIS at j
                dp[i] = max(dp[i], dp[j]+1);
        }
        best = max(best, dp[i]);
    }
    return best;
}

// O(n log n) version using binary search + patience sorting
int lengthOfLIS_nlogn(vector<int>& nums) {
    vector<int> tails; // tails[i] = smallest tail of all IS of length i+1
    for (int x : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end()) tails.push_back(x);  // extend
        else                  *it = x;              // replace
    }
    return (int)tails.size();
}

// LeetCode 1143 — Longest Common Subsequence
// Time: O(m*n)  Space: O(m*n) -> O(n) with rolling array
int longestCommonSubsequence(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    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] = dp[i-1][j-1] + 1;      // chars match: extend
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]); // skip one char
        }
    }
    return dp[m][n];
}

// Space-optimised: O(n) using two rolling rows
int lcs_space(string s1, string s2) {
    int m = s1.size(), n = s2.size();
    vector<int> prev(n+1,0), curr(n+1,0);
    for (int i=1;i<=m;i++) {
        for (int j=1;j<=n;j++)
            curr[j] = s1[i-1]==s2[j-1] ? prev[j-1]+1 : max(prev[j],curr[j-1]);
        swap(prev, curr);
        fill(curr.begin(), curr.end(), 0);
    }
    return prev[n];
}

// 0/1 Knapsack: each item used at most once
// Time: O(n*W)  Space: O(W) with 1D optimisation
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; i++) {
        // CRITICAL: iterate W down to w[i] to prevent using item i twice
        for (int cap = W; cap >= w[i]; cap--) {
            dp[cap] = max(dp[cap], dp[cap - w[i]] + v[i]);
        }
    }
    return dp[W];
}
// Why iterate capacity in REVERSE for 0/1 knapsack?
// When filling dp[cap], we need dp[cap-w[i]] from the PREVIOUS item iteration.
// Iterating forward would update dp[cap-w[i]] first, allowing item i to be
// used multiple times. Reverse iteration preserves the 'at most once' constraint.

// Unbounded Knapsack (items reusable): iterate capacity FORWARD
int unboundedKnapsack(vector<int>& w, vector<int>& v, int W) {
    vector<int> dp(W+1, 0);
    for (int cap = 1; cap <= W; cap++)
        for (int i = 0; i < (int)w.size(); i++)
            if (w[i] <= cap)
                dp[cap] = max(dp[cap], dp[cap - w[i]] + v[i]);
    return dp[W];
}

// Best Time to Buy and Sell Stock with Cooldown (LC 309)
// States: held (holding stock), sold (just sold), rest (cooldown done)
// Time: O(n)  Space: O(1)
int maxProfit(vector<int>& prices) {
    int held = INT_MIN, sold = 0, rest = 0;
    for (int p : prices) {
        int prevHeld = held, prevSold = sold, prevRest = rest;
        held = max(prevHeld, prevRest - p);  // hold: keep or buy from rest
        sold = prevHeld + p;                  // sell: was holding, now sell
        rest = max(prevRest, prevSold);       // rest: keep resting or cooldown
    }
    return max(sold, rest); // can't end holding stock
}
// State transition diagram:
// rest -> held (buy)    held -> sold (sell)    sold -> rest (cooldown)
// rest -> rest (wait)   held -> held (hold)

// LeetCode 312 — Burst Balloons
// dp[l][r] = max coins from bursting all balloons between l and r (exclusive)
// Key: think of k as the LAST balloon to burst in [l,r], not the first.
// Time: O(n^3)  Space: O(n^2)
int maxCoins(vector<int>& nums) {
    int n = nums.size();
    // Pad with sentinel 1s at both ends
    vector<int> a(n+2);
    a[0] = a[n+1] = 1;
    for (int i=0;i<n;i++) a[i+1] = nums[i];
    n += 2;
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // len = length of open interval (l,r)
    for (int len = 2; len < n; len++) {
        for (int l = 0; l < n-len; l++) {
            int r = l + len;
            for (int k = l+1; k < r; k++) { // k is last burst in (l,r)
                dp[l][r] = max(dp[l][r],
                    dp[l][k] + a[l]*a[k]*a[r] + dp[k][r]);
            }
        }
    }
    return dp[0][n-1];
}

// LeetCode 72 — Edit Distance
// Min operations (insert, delete, replace) to convert word1 to word2.
// Time: O(m*n)  Space: O(n) rolling array
int minDistance(string s, string t) {
    int m = s.size(), n = t.size();
    vector<int> dp(n+1);
    iota(dp.begin(), dp.end(), 0); // dp[j] = j (delete j chars from t)
    for (int i = 1; i <= m; i++) {
        int prev = dp[0]; // dp[i-1][j-1] before overwrite
        dp[0] = i;        // dp[i][0] = i (delete i chars from s)
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (s[i-1] == t[j-1])
                dp[j] = prev;           // chars match: no operation
            else
                dp[j] = 1 + min({prev,  // replace
                                 dp[j],  // delete from s
                                 dp[j-1]}); // insert into s
            prev = temp;
        }
    }
    return dp[n];
}

// LeetCode 62 — Unique Paths
// Count paths from top-left to bottom-right moving only right or down.
// Time: O(m*n)  Space: O(n)
int uniquePaths(int m, int n) {
    vector<int> dp(n, 1); // first row: all 1s (only rightward path)
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[j] += dp[j-1]; // paths from top + paths from left
    return dp[n-1];
}
// Mathematical answer: C(m+n-2, m-1) — choose m-1 down moves from m+n-2 total.

// LC 63 — Unique Paths II (with obstacles)
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<long long> dp(n, 0);
    dp[0] = grid[0][0] == 0 ? 1 : 0;
    for (int i = 0; i < m; i++) {
        if (grid[i][0] == 1) dp[0] = 0; // obstacle blocks leftmost column
        for (int j = 1; j < n; j++)
            dp[j] = grid[i][j] == 1 ? 0 : dp[j] + dp[j-1];
    }
    return (int)dp[n-1];
}

// LeetCode 139 — Word Break
// Can string s be segmented into words from wordDict?
// Time: O(n^2 * L)  L=avg word length  Space: O(n)
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> ws(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n+1, false);
    dp[0] = true; // empty string always segmentable
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // If prefix s[0..j-1] is breakable AND s[j..i-1] is a word
            if (dp[j] && ws.count(s.substr(j, i-j))) {
                dp[i] = true;
                break; // found one valid split, no need to check more
            }
        }
    }
    return dp[n];
}

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // dp[i] = minimum coins needed to make amount i
        vector<int> dp(amount+1, amount+1); // sentinel: larger than any valid answer
        dp[0] = 0;  // base case

        for (int i = 1; i <= amount; i++) {
            for (int c : coins) {
                if (c <= i)  // coin c can contribute to amount i
                    dp[i] = min(dp[i], dp[i-c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        // Space-optimised: use two rows only
        vector<int> prev(n+1, 0), curr(n+1, 0);

        for (int i = 1; i <= m; i++) {
            fill(curr.begin(), curr.end(), 0);
            for (int j = 1; j <= n; j++) {
                if (text1[i-1] == text2[j-1])
                    curr[j] = prev[j-1] + 1;         // chars match
                else
                    curr[j] = max(prev[j], curr[j-1]); // skip one
            }
            swap(prev, curr);
        }
        return prev[n];
    }
};