dp_1d.cpp

/*
1D Dynamic Programming
Mathematical Foundation: dp[i] = f(dp[j]) for j < i
Optimal substructure: optimal solution contains optimal solutions to subproblems
Overlapping subproblems: memoization avoids recomputation
Time: O(n), Space: O(n) → O(1) with space optimization
*/

#include <bits/stdc++.h>
using namespace std;

// Fibonacci (Basic DP)
// LeetCode: 509. Fibonacci Number
// https://leetcode.com/problems/fibonacci-number/
// Related:
// 70. Climbing Stairs
// https://leetcode.com/problems/climbing-stairs/
// 1137. N-th Tribonacci Number
// https://leetcode.com/problems/n-th-tribonacci-number/
// 746. Min Cost Climbing Stairs
// https://leetcode.com/problems/min-cost-climbing-stairs/
int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

// Climbing Stairs (Classic DP)
// LeetCode: 70. Climbing Stairs
// https://leetcode.com/problems/climbing-stairs/
// Related:
// 746. Min Cost Climbing Stairs
// https://leetcode.com/problems/min-cost-climbing-stairs/
// 1137. N-th Tribonacci Number
// https://leetcode.com/problems/n-th-tribonacci-number/
// 91. Decode Ways
// https://leetcode.com/problems/decode-ways/
// 509. Fibonacci Number
// https://leetcode.com/problems/fibonacci-number/
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;
}

// House Robber (Skip Adjacent DP)
// LeetCode: 198. House Robber
// https://leetcode.com/problems/house-robber/
// Related:
// 213. House Robber II
// https://leetcode.com/problems/house-robber-ii/
// 337. House Robber III
// https://leetcode.com/problems/house-robber-iii/
// 740. Delete and Earn
// https://leetcode.com/problems/delete-and-earn/
// 2320. Count Number of Ways to Place Houses
// https://leetcode.com/problems/count-number-of-ways-to-place-houses/
int rob(vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int x : nums) {
        int temp = max(curr, prev + x);
        prev = curr;
        curr = temp;
    }
    return curr;
}

// House Robber II - Circular Array DP
// LeetCode: 213. House Robber II
// https://leetcode.com/problems/house-robber-ii/
// Related:
// 198. House Robber
// https://leetcode.com/problems/house-robber/
// 740. Delete and Earn
// https://leetcode.com/problems/delete-and-earn/
// 256. Paint House
// https://leetcode.com/problems/paint-house/
// 265. Paint House II
// https://leetcode.com/problems/paint-house-ii/
int robCircular(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    
    auto robLinear = [](vector<int>& a, int start, int end) {
        int prev = 0, curr = 0;
        for (int i = start; i <= end; i++) {
            int temp = max(curr, prev + a[i]);
            prev = curr;
            curr = temp;
        }
        return curr;
    };
    
    return max(robLinear(nums, 0, nums.size() - 2), 
               robLinear(nums, 1, nums.size() - 1));
}

// Decode Ways (String DP)
// LeetCode: 91. Decode Ways
// https://leetcode.com/problems/decode-ways/
// Related:
// 639. Decode Ways II
// https://leetcode.com/problems/decode-ways-ii/
// 70. Climbing Stairs
// https://leetcode.com/problems/climbing-stairs/
// 2266. Count Number of Texts
// https://leetcode.com/problems/count-number-of-texts/
// 1277. Count Square Submatrices with All Ones
// https://leetcode.com/problems/count-square-submatrices-with-all-ones/
int numDecodings(string s) {
    int n = s.size();
    if (n == 0 || s[0] == '0') return 0;
    int prev2 = 1, prev1 = 1;
    
    for (int i = 1; i < n; i++) {
        int curr = 0;
        if (s[i] != '0') curr += prev1;
        int two = stoi(s.substr(i - 1, 2));
        if (two >= 10 && two <= 26) curr += prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

// Word Break (String DP with Dictionary)
// LeetCode: 139. Word Break
// https://leetcode.com/problems/word-break/
// Related:
// 140. Word Break II
// https://leetcode.com/problems/word-break-ii/
// 472. Concatenated Words
// https://leetcode.com/problems/concatenated-words/
// 1048. Longest String Chain
// https://leetcode.com/problems/longest-string-chain/
// 2707. Extra Characters in a String
// https://leetcode.com/problems/extra-characters-in-a-string/
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1);
    dp[0] = true;
    
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

// Coin Change (Unbounded Knapsack DP)
// LeetCode: 322. Coin Change
// https://leetcode.com/problems/coin-change/
// Related:
// 518. Coin Change 2
// https://leetcode.com/problems/coin-change-2/
// 377. Combination Sum IV
// https://leetcode.com/problems/combination-sum-iv/
// 279. Perfect Squares
// https://leetcode.com/problems/perfect-squares/
// 983. Minimum Cost For Tickets
// https://leetcode.com/problems/minimum-cost-for-tickets/
// 1449. Form Largest Integer With Digits That Add up to Target
// https://leetcode.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// Longest Increasing Subsequence (LIS - Binary Search Optimization)
// LeetCode: 300. Longest Increasing Subsequence
// https://leetcode.com/problems/longest-increasing-subsequence/
// Related:
// 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 1105. Filling Bookcase Shelves
// https://leetcode.com/problems/filling-bookcase-shelves/
// 673. Number of Longest Increasing Subsequence
// https://leetcode.com/problems/number-of-longest-increasing-subsequence/
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();
}

// Perfect Squares (Mathematical DP)
// LeetCode: 279. Perfect Squares
// https://leetcode.com/problems/perfect-squares/
// Related:
// 322. Coin Change
// https://leetcode.com/problems/coin-change/
// 264. Ugly Number II
// https://leetcode.com/problems/ugly-number-ii/
// 204. Count Primes
// https://leetcode.com/problems/count-primes/
// 343. Integer Break
// https://leetcode.com/problems/integer-break/
// 650. 2 Keys Keyboard
// https://leetcode.com/problems/2-keys-keyboard/
int numSquares(int n) {
    vector<int> dp(n + 1, n);
    dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

// Jump Game (Greedy/DP Approach)
// LeetCode: 55. Jump Game
// https://leetcode.com/problems/jump-game/
// Related:
// 45. Jump Game II
// https://leetcode.com/problems/jump-game-ii/
// 1306. Jump Game III
// https://leetcode.com/problems/jump-game-iii/
// 1696. Jump Game VI
// https://leetcode.com/problems/jump-game-vi/
// 1340. Jump Game V
// https://leetcode.com/problems/jump-game-v/
// 1871. Jump Game VII
// https://leetcode.com/problems/jump-game-vii/
bool canJump(vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > reach) return false;
        reach = max(reach, i + nums[i]);
    }
    return true;
}

// Jump Game II (Minimum Jumps - Greedy Optimization)
// LeetCode: 45. Jump Game II
// https://leetcode.com/problems/jump-game-ii/
// Related:
// 55. Jump Game
// https://leetcode.com/problems/jump-game/
// 1024. Video Stitching
// https://leetcode.com/problems/video-stitching/
// 1326. Minimum Number of Taps to Open to Water a Garden
// https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/
// 1306. Jump Game III
// https://leetcode.com/problems/jump-game-iii/
// 1696. Jump Game VI
// https://leetcode.com/problems/jump-game-vi/
int jump(vector<int>& nums) {
    int jumps = 0, curEnd = 0, curFar = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        curFar = max(curFar, i + nums[i]);
        if (i == curEnd) {
            jumps++;
            curEnd = curFar;
        }
    }
    return jumps;
}