Dynamic Programming

unordered_map<State, Result> memo;
 
Result solve(State state) {
    // Base case
    if (isBase(state)) return baseResult(state);
 
    // Check cache
    if (memo.count(state)) return memo[state];
 
    // Compute and cache
    Result result = /* combine recursive calls */;
    return memo[state] = result;
}

// Without memoization: O(2^n)
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}
 
// With memoization: O(n)
vector<int> memo(n+1, -1);
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// 1. Define the DP array: dp[state] = answer for that state
// 2. Initialize base cases
// 3. Fill in larger states using smaller states
// 4. Return the answer (often dp[n] or dp[n][m])
 
vector<int> dp(n+1, 0);   // Or 2D: vector<vector<int>> dp(m+1, vector<int>(n+1, 0))
// Initialize base cases
dp[0] = 1;  // (varies by problem)
// Fill iteratively
for (int i = 1; i <= n; i++) {
    dp[i] = /* transition using dp[i-1], dp[i-2], ... */;
}
return dp[n];

// 2D → 1D when dp[i][j] only depends on dp[i-1][...]
vector<int> dp(n+1, 0);   // Single array, reused each row
 
for (int i = 1; i <= m; i++) {
    for (int j = n; j >= 0; j--) {   // Reverse order for 0/1 knapsack!
        dp[j] = /* transition */;
    }
}
 
// 1D with two variables for Fibonacci-like:
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}

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;
}
// Time: O(n), Space: O(1)

int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    int prev2 = nums[0], 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;
}
// State: dp[i] = max money from houses 0..i
// Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// Time: O(n), Space: O(1)

int numDecodings(string s) {
    int n = s.size();
    // dp[i] = number of ways to decode s[0..i-1]
    vector<int> dp(n+1, 0);
    dp[0] = 1;                         // Empty string: 1 way
    dp[1] = s[0] != '0' ? 1 : 0;      // Single digit
 
    for (int i = 2; i <= n; i++) {
        int oneDigit = s[i-1] - '0';
        int twoDigit = stoi(s.substr(i-2, 2));
 
        if (oneDigit >= 1)                        // Valid single digit
            dp[i] += dp[i-1];
        if (twoDigit >= 10 && twoDigit <= 26)     // Valid double digit
            dp[i] += dp[i-2];
    }
    return dp[n];
}
// Time: O(n), Space: O(n) → optimizable to O(1)

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n+1, false);
    dp[0] = true;   // Empty string: can always be segmented
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i-j))) {
                dp[i] = true; break;
            }
        }
    }
    return dp[n];
}
// dp[i] = can s[0..i-1] be segmented using words in dict?
// Transition: dp[i] = OR over all j < i of (dp[j] && s[j..i-1] in dict)
// Time: O(n² × L) where L = avg word length, Space: O(n)

int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));  // First row/col = 1
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}
// Space-optimized to 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-1];
    return dp[n-1];
}
// Time: O(m×n), Space: O(n)

int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            else if (i == 0) grid[i][j] += grid[i][j-1];
            else if (j == 0) grid[i][j] += grid[i-1][j];
            else grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
        }
    return grid[m-1][n-1];
}
// Modifies grid in-place. Time: O(m×n), Space: O(1)

int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), maxSide = 0;
    vector<vector<int>> dp(m, vector<int>(n, 0));
 
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '0') continue;
            if (i == 0 || j == 0) dp[i][j] = 1;
            else dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            maxSide = max(maxSide, dp[i][j]);
        }
    }
    return maxSide * maxSide;
}
// dp[i][j] = side length of largest square with bottom-right at (i,j)
// Key insight: limited by smallest of three neighbors
// Time: O(m×n), Space: O(m×n) → O(n) with rolling array

int knapsack01(int W, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    // dp[i][w] = max value using first i items with capacity w
    // dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i]] + values[i])
 
    // Space-optimized 1D (must traverse W in REVERSE to avoid reuse)
    vector<int> dp(W+1, 0);
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {  // ← REVERSE order
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
        }
    }
    return dp[W];
}
// Time: O(n×W), Space: O(W)
// The REVERSE traversal ensures each item is used AT MOST ONCE

int unboundedKnapsack(int W, vector<int>& weights, vector<int>& values) {
    vector<int> dp(W+1, 0);
    for (int i = 0; i < (int)weights.size(); i++) {
        for (int w = weights[i]; w <= W; w++) {  // ← FORWARD order
            dp[w] = max(dp[w], dp[w-weights[i]] + values[i]);
        }
    }
    return dp[W];
}
// The FORWARD traversal allows each item to be reused

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);   // Initialize to impossible value
    dp[0] = 0;
 
    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a) {
                dp[a] = min(dp[a], dp[a-coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
// Time: O(amount × coins), Space: O(amount)
 
// Alternative: iterate coins in outer loop (equivalent for unbounded)
for (int coin : coins)
    for (int a = coin; a <= amount; a++)
        dp[a] = min(dp[a], dp[a-coin] + 1);

bool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;
    int target = total / 2;
 
    vector<bool> dp(target+1, false);
    dp[0] = true;   // Can always make sum 0 (empty subset)
 
    for (int x : nums) {
        for (int j = target; j >= x; j--) {   // Reverse: each element used once
            dp[j] = dp[j] || dp[j-x];
        }
    }
    return dp[target];
}
// Time: O(n × target), Space: O(target)

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount+1, 0);
    dp[0] = 1;   // 1 way to make 0: use no coins
 
    for (int coin : coins) {             // Outer loop: COINS (ensures no duplicates)
        for (int a = coin; a <= amount; a++) {   // Inner: forward (unbounded)
            dp[a] += dp[a-coin];
        }
    }
    return dp[amount];
}
// NOTE: If we loop amount first then coins, we'd count permutations (not combinations)
// Coin outer loop ensures each combination is counted once
// Time: O(amount × coins), Space: O(amount)

int longestCommonSubsequence(string s, string t) {
    int m = s.size(), n = t.size();
    // dp[i][j] = LCS length of s[0..i-1] and t[0..j-1]
    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 (s[i-1] == t[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;    // Characters match
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  // Skip one char
        }
    }
    return dp[m][n];
}
// Time: O(m×n), Space: O(m×n) → O(n) with rolling array
 
/*
  s = "abcde", t = "ace"
  dp table:
       ""  a  c  e
  ""  [ 0  0  0  0]
  a   [ 0  1  1  1]
  b   [ 0  1  1  1]
  c   [ 0  1  2  2]
  d   [ 0  1  2  2]
  e   [ 0  1  2  3]  ← LCS = "ace" length 3
*/

int minDistance(string s, string t) {
    int m = s.size(), n = t.size();
    // dp[i][j] = min edits to convert s[0..i-1] to t[0..j-1]
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
 
    // Base cases: convert to/from empty string
    for (int i = 0; i <= m; i++) dp[i][0] = i;  // Delete all s chars
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // Insert all t chars
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1];            // No operation needed
            } else {
                dp[i][j] = 1 + min({
                    dp[i-1][j],      // Delete s[i-1]
                    dp[i][j-1],      // Insert t[j-1]
                    dp[i-1][j-1]     // Replace s[i-1] with t[j-1]
                });
            }
        }
    }
    return dp[m][n];
}
// Time: O(m×n), Space: O(m×n)

int longestPalindromeSubseq(string s) {
    int n = s.size();
    // dp[i][j] = LPS length of s[i..j]
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = 1;  // Single char
 
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s[i] == s[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
        }
    }
    return dp[0][n-1];
}
// Time: O(n²), Space: O(n²)

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    // dp[i][j] = does s[0..i-1] match p[0..j-1]?
    vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
    dp[0][0] = true;   // Empty string matches empty pattern
 
    // p starting with '*' can match empty s
    for (int j = 1; j <= n; j++)
        if (p[j-1] == '*') dp[0][j] = dp[0][j-1];
 
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*')
                dp[i][j] = dp[i-1][j]     // '*' matches one more char of s
                          || dp[i][j-1];   // '*' matches zero chars
            else if (p[j-1] == '?' || s[i-1] == p[j-1])
                dp[i][j] = dp[i-1][j-1];  // Current chars match
        }
    }
    return dp[m][n];
}
// Time: O(m×n), Space: O(m×n)

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    // dp[i] = length of LIS ending at index i
    vector<int> dp(n, 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);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}
// Time: O(n²), Space: O(n)

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;  // tails[k] = smallest tail element of any IS of length k+1
 
    for (int x : nums) {
        // Find first position in tails where tails[pos] >= x
        int pos = lower_bound(tails.begin(), tails.end(), x) - tails.begin();
 
        if (pos == (int)tails.size())
            tails.push_back(x);   // x extends the longest IS
        else
            tails[pos] = x;       // x is a better (smaller) tail for IS of length pos+1
    }
    return tails.size();
}
// Time: O(n log n), Space: O(n)
 
/*
  nums = [10, 9, 2, 5, 3, 7, 101, 18]
  Process 10: tails=[10]
  Process 9:  find pos for 9 in [10] → pos=0, replace → tails=[9]
  Process 2:  pos=0, replace → tails=[2]
  Process 5:  pos=1, extend → tails=[2,5]
  Process 3:  pos=1, replace → tails=[2,3]
  Process 7:  pos=2, extend → tails=[2,3,7]
  Process 101: pos=3, extend → tails=[2,3,7,101]
  Process 18: pos=3, replace → tails=[2,3,7,18]
  Length = tails.size() = 4 ✓
*/

// dp[l][r] = answer for the subproblem on interval [l, r]
vector<vector<int>> dp(n, vector<int>(n, 0));
 
// Fill by increasing length
for (int len = 2; len <= n; len++) {           // Interval length
    for (int l = 0; l + len - 1 < n; l++) {   // Left endpoint
        int r = l + len - 1;                   // Right endpoint
        dp[l][r] = INITIAL_VALUE;
        for (int k = l; k < r; k++) {          // Split point / last step
            dp[l][r] = combine(dp[l][k], dp[k+1][r], /* k cost */);
        }
    }
}

int maxCoins(vector<int>& nums) {
    // Add sentinel balloons of value 1 at both ends
    nums.insert(nums.begin(), 1);
    nums.push_back(1);
    int n = nums.size();
 
    // dp[l][r] = max coins from bursting all balloons in open interval (l, r)
    vector<vector<int>> dp(n, vector<int>(n, 0));
 
    for (int len = 2; len < n; len++) {
        for (int l = 0; l + len < n; l++) {
            int r = l + len;
            for (int k = l+1; k < r; k++) {
                // k is the LAST balloon burst in (l, r)
                dp[l][r] = max(dp[l][r],
                    dp[l][k] + nums[l]*nums[k]*nums[r] + dp[k][r]);
            }
        }
    }
    return dp[0][n-1];
}
// Time: O(n³), Space: O(n²)

int minCut(string s) {
    int n = s.size();
    // Precompute palindrome table
    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
    for (int i = n-1; i >= 0; i--)
        for (int j = i; j < n; j++)
            isPalin[i][j] = (s[i]==s[j]) && (j-i<2 || isPalin[i+1][j-1]);
 
    // dp[i] = min cuts for s[0..i]
    vector<int> dp(n, 0);
    for (int i = 1; i < n; i++) {
        if (isPalin[0][i]) { dp[i] = 0; continue; }  // Whole prefix is palindrome
        dp[i] = i;   // Max cuts = i (cut every character)
        for (int j = 1; j <= i; j++) {
            if (isPalin[j][i]) dp[i] = min(dp[i], dp[j-1] + 1);
        }
    }
    return dp[n-1];
}
// Time: O(n²), Space: O(n²)

// Returns {rob_this_node, skip_this_node}
pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0, 0};
 
    auto [leftRob, leftSkip] = dfs(node->left);
    auto [rightRob, rightSkip] = dfs(node->right);
 
    // If we rob this node: cannot rob children
    int rob = node->val + leftSkip + rightSkip;
 
    // If we skip this node: children may or may not be robbed (take max)
    int skip = max(leftRob, leftSkip) + max(rightRob, rightSkip);
 
    return {rob, skip};
}
 
int rob(TreeNode* root) {
    auto [robRoot, skipRoot] = dfs(root);
    return max(robRoot, skipRoot);
}
// Time: O(n), Space: O(h) recursion stack

// (Revisit from Ch10 with DP framing)
// dp[node] = max gain this node contributes going UPWARD (one direction)
// Update globalMax with node.val + leftGain + rightGain (can use both sides)
int maxPathSum(TreeNode* root) {
    int globalMax = INT_MIN;
    function<int(TreeNode*)> dp = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int L = max(0, dp(node->left));
        int R = max(0, dp(node->right));
        globalMax = max(globalMax, node->val + L + R);
        return node->val + max(L, R);
    };
    dp(root);
    return globalMax;
}

// dp[mask][i] = min cost to visit all cities in mask, ending at city i
int tsp(int n, vector<vector<int>>& dist) {
    int FULL = (1 << n) - 1;
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX/2));
    dp[1][0] = 0;   // Start at city 0
 
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u))) continue;   // u must be in mask
            if (dp[mask][u] == INT_MAX/2) continue;
 
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;   // v must NOT be in mask
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
 
    // Return to starting city (0) after visiting all
    int ans = INT_MAX;
    for (int u = 1; u < n; u++)
        if (dp[FULL][u] != INT_MAX/2)
            ans = min(ans, dp[FULL][u] + dist[u][0]);
    return ans;
}
// Time: O(2^n × n²), Space: O(2^n × n)

// dp[mask][i] = length of shortest superstring using words in mask, ending with words[i]
// Greedy: always extend with minimum overlap

int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX, maxProfit = 0;
    for (int p : prices) {
        minPrice  = min(minPrice, p);
        maxProfit = max(maxProfit, p - minPrice);
    }
    return maxProfit;
}

// State: hold (have stock), free (no stock)
int maxProfit(vector<int>& prices) {
    int hold = -prices[0], free = 0;
    for (int i = 1; i < (int)prices.size(); i++) {
        int newHold = max(hold, free - prices[i]);   // Hold or buy today
        int newFree = max(free, hold + prices[i]);   // Keep free or sell today
        hold = newHold; free = newFree;
    }
    return free;
}

// States: hold, sold (just sold, cooldown), rest (can buy)
int maxProfit(vector<int>& prices) {
    int hold = -prices[0], sold = 0, rest = 0;
    for (int i = 1; i < (int)prices.size(); i++) {
        int prevHold = hold, prevSold = sold, prevRest = rest;
        hold = max(prevHold, prevRest - prices[i]);  // Hold or buy (from rest)
        sold = prevHold + prices[i];                  // Sell (must be in cooldown next)
        rest = max(prevRest, prevSold);               // Rest or come off cooldown
    }
    return max(sold, rest);
}

int maxProfit(vector<int>& prices, int fee) {
    int hold = -prices[0], free = 0;
    for (int i = 1; i < (int)prices.size(); i++) {
        int newHold = max(hold, free - prices[i]);
        int newFree = max(free, hold + prices[i] - fee);  // Deduct fee on sell
        hold = newHold; free = newFree;
    }
    return free;
}

// ❌ State doesn't capture enough information
// Problem: max profit from stock with at most k transactions
int dp[n];   // dp[i] = max profit up to day i — WRONG: doesn't track transactions
 
// ✅ Correct state
int dp[n][k+1];  // dp[i][j] = max profit up to day i using j transactions

// 0/1 Knapsack: each item used AT MOST once
// ❌ Forward traversal allows reuse
for (int w = 0; w <= W; w++) dp[w] = max(dp[w], dp[w-weight]+value);  // WRONG
 
// ✅ Reverse traversal prevents reuse
for (int w = W; w >= weight; w--) dp[w] = max(dp[w], dp[w-weight]+value);
 
// Unbounded Knapsack: item can be reused → forward traversal is correct!

// Edit distance:
// ❌ Forgot to initialize first row/column
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// First row: dp[0][j] = j (delete j chars to make empty)
// First col: dp[i][0] = i (insert i chars to match prefix)
// Without initialization → wrong answers for strings starting with empty

// LCS with 1-indexed DP: dp[i][j] refers to s[i-1] and t[j-1]
if (s[i-1] == t[j-1])  // Correct: 1-indexed dp, 0-indexed strings
if (s[i]   == t[j])    // Wrong: if dp is 1-indexed

// dp initialized to INT_MAX, then adding to it → overflow
int dp[W+1];
fill(dp, dp+W+1, INT_MAX);
dp[a] = dp[a-coin] + 1;  // ❌ If dp[a-coin] == INT_MAX → overflow!
 
// ✅ Use a large but safe sentinel
fill(dp, dp+W+1, amount+1);  // amount+1 > any valid answer → safe

int climbStairs(int n) {
    if (n<=2) return n;
    int a=1,b=2;
    for(int i=3;i<=n;i++){int c=a+b;a=b;b=c;}
    return b;
}
// Time: O(n), Space: O(1)

int rob(vector<int>& nums) {
    int prev2=0,prev1=0;
    for(int x:nums){int curr=max(prev1,prev2+x);prev2=prev1;prev1=curr;}
    return prev1;
}
// Time: O(n), Space: O(1)

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);
    dp[0]=0;
    for(int a=1;a<=amount;a++)
        for(int c:coins)
            if(c<=a) dp[a]=min(dp[a],dp[a-c]+1);
    return dp[amount]>amount?-1:dp[amount];
}
// Time: O(amount × coins), Space: O(amount)

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-1];
    return dp[n-1];
}
// Time: O(m×n), Space: O(n)

int longestCommonSubsequence(string s, string t) {
    int m=s.size(),n=t.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++)
        dp[i][j]=s[i-1]==t[j-1]?dp[i-1][j-1]+1:max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}
// Time: O(m×n), Space: O(m×n)

int minDistance(string s, string t) {
    int m=s.size(),n=t.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    for(int i=0;i<=m;i++) dp[i][0]=i;
    for(int j=0;j<=n;j++) dp[0][j]=j;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
        dp[i][j]=s[i-1]==t[j-1]?dp[i-1][j-1]:1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});
    return dp[m][n];
}
// Time: O(m×n), Space: O(m×n)

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for(int x:nums){
        auto it=lower_bound(tails.begin(),tails.end(),x);
        if(it==tails.end()) tails.push_back(x);
        else *it=x;
    }
    return tails.size();
}
// Time: O(n log n), Space: O(n)

bool canPartition(vector<int>& nums) {
    int sum=accumulate(nums.begin(),nums.end(),0);
    if(sum%2) return false;
    int T=sum/2;
    vector<bool> dp(T+1,false);
    dp[0]=true;
    for(int x:nums) for(int j=T;j>=x;j--) dp[j]=dp[j]||dp[j-x];
    return dp[T];
}
// Time: O(n×T), Space: O(T)

int maxCoins(vector<int>& nums) {
    nums.insert(nums.begin(),1); nums.push_back(1);
    int n=nums.size();
    vector<vector<int>> dp(n,vector<int>(n,0));
    for(int len=2;len<n;len++)
        for(int l=0;l+len<n;l++){
            int r=l+len;
            for(int k=l+1;k<r;k++)
                dp[l][r]=max(dp[l][r],dp[l][k]+nums[l]*nums[k]*nums[r]+dp[k][r]);
        }
    return dp[0][n-1];
}
// Time: O(n³), Space: O(n²)

int rob(TreeNode* root) {
    function<pair<int,int>(TreeNode*)> dfs=[&](TreeNode* node)->pair<int,int>{
        if(!node) return {0,0};
        auto[lr,ls]=dfs(node->left);
        auto[rr,rs]=dfs(node->right);
        return {node->val+ls+rs, max(lr,ls)+max(rr,rs)};
    };
    auto[r,s]=dfs(root);
    return max(r,s);
}
// Time: O(n), Space: O(h)

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(),wordDict.end());
    int n=s.size();
    vector<bool> dp(n+1,false);
    dp[0]=true;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            if(dp[j]&&dict.count(s.substr(j,i-j))){dp[i]=true;break;}
    return dp[n];
}
// Time: O(n² × L), Space: O(n)

int maxProfit(vector<int>& prices) {
    int hold=INT_MIN, sold=0, rest=0;
    hold=-prices[0];
    for(int i=1;i<(int)prices.size();i++){
        int ph=hold,ps=sold,pr=rest;
        hold=max(ph,pr-prices[i]);
        sold=ph+prices[i];
        rest=max(pr,ps);
    }
    return max(sold,rest);
}
// Time: O(n), Space: O(1)