dp_2d.cpp

/*
2D Dynamic Programming
Mathematical Foundation: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
State depends on multiple dimensions
Common patterns: grid path, string matching, interval DP
Time: O(n*m), Space: O(n*m) → O(min(n,m)) with rolling array
*/

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

// Unique Paths (Grid Path DP)
// LeetCode: 62. Unique Paths
// https://leetcode.com/problems/unique-paths/
// Related:
// 63. Unique Paths II
// https://leetcode.com/problems/unique-paths-ii/
// 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// 174. Dungeon Game
// https://leetcode.com/problems/dungeon-game/
// 1594. Maximum Non Negative Product in a Matrix
// https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
// 576. Out of Boundary Paths
// https://leetcode.com/problems/out-of-boundary-paths/
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];
}

// Unique Paths II (Grid Path with Obstacles)
// LeetCode: 63. Unique Paths II
// https://leetcode.com/problems/unique-paths-ii/
// Related:
// 62. Unique Paths
// https://leetcode.com/problems/unique-paths/
// 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// 980. Unique Paths III
// https://leetcode.com/problems/unique-paths-iii/
// 1210. Minimum Moves to Reach Target with Rotations
// https://leetcode.com/problems/minimum-moves-to-reach-target-with-rotations/
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, 0);
    dp[0] = 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) dp[j] = 0;
            else if (j > 0) dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

// Minimum Path Sum
// LeetCode: 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// Related:
// 62. Unique Paths
// https://leetcode.com/problems/unique-paths/
// 63. Unique Paths II
// https://leetcode.com/problems/unique-paths-ii/
// 174. Dungeon Game
// https://leetcode.com/problems/dungeon-game/
// 931. Minimum Falling Path Sum
// https://leetcode.com/problems/minimum-falling-path-sum/
// 1289. Minimum Falling Path Sum II
// https://leetcode.com/problems/minimum-falling-path-sum-ii/
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;
    
    for (int i = 0; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++)
            dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
    }
    return dp[n - 1];
}

// Edit Distance (Levenshtein Distance)
// LeetCode: 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
// Related:
// 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// 583. Delete Operation for Two Strings
// https://leetcode.com/problems/delete-operation-for-two-strings/
// 712. Minimum ASCII Delete Sum for Two Strings
// https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/
// 161. One Edit Distance
// https://leetcode.com/problems/one-edit-distance/
// 97. Interleaving String
// https://leetcode.com/problems/interleaving-string/
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<int> dp(n + 1);
    iota(dp.begin(), dp.end(), 0);
    
    for (int i = 1; i <= m; i++) {
        int prev = dp[0];
        dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (word1[i - 1] == word2[j - 1]) dp[j] = prev;
            else dp[j] = 1 + min({dp[j], dp[j - 1], prev});
            prev = temp;
        }
    }
    return dp[n];
}

// Longest Common Subsequence
// LeetCode: 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// Related:
// 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
// 1035. Uncrossed Lines
// https://leetcode.com/problems/uncrossed-lines/
// 718. Maximum Length of Repeated Subarray
// https://leetcode.com/problems/maximum-length-of-repeated-subarray/
// 1092. Shortest Common Supersequence
// https://leetcode.com/problems/shortest-common-supersequence/
// 1639. Number of Ways to Form a Target String Given a Dictionary
// https://leetcode.com/problems/number-of-ways-to-form-a-target-string-given-a-dictionary/
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<int> dp(n + 1, 0);
    
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) dp[j] = prev + 1;
            else dp[j] = max(dp[j], dp[j - 1]);
            prev = temp;
        }
    }
    return dp[n];
}

// Maximal Square
// LeetCode: 221. Maximal Square
// https://leetcode.com/problems/maximal-square/
// Related:
// 85. Maximal Rectangle
// https://leetcode.com/problems/maximal-rectangle/
// 1277. Count Square Submatrices with All Ones
// https://leetcode.com/problems/count-square-submatrices-with-all-ones/
// 1504. Count Submatrices With All Ones
// https://leetcode.com/problems/count-submatrices-with-all-ones/
// 304. Range Sum Query 2D - Immutable
// https://leetcode.com/problems/range-sum-query-2d-immutable/
int maximalSquare(vector<vector<char>>& matrix) {
    int m = matrix.size(), n = matrix[0].size(), maxSide = 0;
    vector<int> dp(n + 1, 0);
    
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (matrix[i - 1][j - 1] == '1') {
                dp[j] = min({dp[j], dp[j - 1], prev}) + 1;
                maxSide = max(maxSide, dp[j]);
            } else dp[j] = 0;
            prev = temp;
        }
    }
    return maxSide * maxSide;
}

// Dungeon Game
// LeetCode: 174. Dungeon Game
// https://leetcode.com/problems/dungeon-game/
// Related:
// 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// 931. Minimum Falling Path Sum
// https://leetcode.com/problems/minimum-falling-path-sum/
// 1594. Maximum Non Negative Product in a Matrix
// https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
// 1463. Cherry Pickup II
// https://leetcode.com/problems/cherry-pickup-ii/
// 741. Cherry Pickup
// https://leetcode.com/problems/cherry-pickup/
int calculateMinimumHP(vector<vector<int>>& dungeon) {
    int m = dungeon.size(), n = dungeon[0].size();
    vector<int> dp(n + 1, INT_MAX);
    dp[n - 1] = 1;
    
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            dp[j] = max(1, min(dp[j], dp[j + 1]) - dungeon[i][j]);
        }
    }
    return dp[0];
}

// Triangle (Minimum Path Sum in Triangle)
// LeetCode: 120. Triangle
// https://leetcode.com/problems/triangle/
// Related:
// 931. Minimum Falling Path Sum
// https://leetcode.com/problems/minimum-falling-path-sum/
// 1289. Minimum Falling Path Sum II
// https://leetcode.com/problems/minimum-falling-path-sum-ii/
// 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// 1301. Number of Paths with Max Score
// https://leetcode.com/problems/number-of-paths-with-max-score/
int minimumTotal(vector<vector<int>>& triangle) {
    vector<int> dp = triangle.back();
    for (int i = triangle.size() - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
        }
    }
    return dp[0];
}

// Regular Expression Matching
// LeetCode: 10. Regular Expression Matching
// https://leetcode.com/problems/regular-expression-matching/
// Related:
// 44. Wildcard Matching
// https://leetcode.com/problems/wildcard-matching/
// 87. Scramble String
// https://leetcode.com/problems/scramble-string/
// 115. Distinct Subsequences
// https://leetcode.com/problems/distinct-subsequences/
// 1316. Distinct Echo Substrings
// https://leetcode.com/problems/distinct-echo-substrings/
bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    
    for (int j = 2; j <= n; j += 2) {
        if (p[j - 1] == '*') dp[j] = dp[j - 2];
    }
    
    for (int i = 1; i <= m; i++) {
        bool prev = dp[0];
        dp[0] = false;
        for (int j = 1; j <= n; j++) {
            bool temp = dp[j];
            if (p[j - 1] == '*') {
                dp[j] = dp[j - 2] || 
                       (dp[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
            } else {
                dp[j] = prev && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
            prev = temp;
        }
    }
    return dp[n];
}

// Burst Balloons (Interval DP)
// LeetCode: 312. Burst Balloons
// https://leetcode.com/problems/burst-balloons/
// Related:
// 1024. Video Stitching
// https://leetcode.com/problems/video-stitching/
// 1039. Minimum Score Triangulation of Polygon
// https://leetcode.com/problems/minimum-score-triangulation-of-polygon/
// 1140. Stone Game II
// https://leetcode.com/problems/stone-game-ii/
// 516. Longest Palindromic Subsequence
// https://leetcode.com/problems/longest-palindromic-subsequence/
// 87. Scramble String
// https://leetcode.com/problems/scramble-string/
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 = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = max(dp[i][j], 
                              dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
            }
        }
    }
    return dp[0][n - 1];
}

// Palindromic Substrings (String DP)
// LeetCode: 647. Palindromic Substrings
// https://leetcode.com/problems/palindromic-substrings/
// Related:
// 5. Longest Palindromic Substring
// https://leetcode.com/problems/longest-palindromic-substring/
// 516. Longest Palindromic Subsequence
// https://leetcode.com/problems/longest-palindromic-subsequence/
// 1312. Minimum Insertion Steps to Make a String Palindrome
// https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// 131. Palindrome Partitioning
// https://leetcode.com/problems/palindrome-partitioning/
int countSubstrings(string s) {
    int n = s.size(), count = 0;
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    
    for (int len = 1; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (len == 1) dp[i][j] = true;
            else if (len == 2) dp[i][j] = (s[i] == s[j]);
            else dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
            if (dp[i][j]) count++;
        }
    }
    return count;
}

// Longest Palindromic Subsequence
// LeetCode: 516. Longest Palindromic Subsequence
// https://leetcode.com/problems/longest-palindromic-subsequence/
// Related:
// 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// 647. Palindromic Substrings
// https://leetcode.com/problems/palindromic-substrings/
// 1312. Minimum Insertion Steps to Make a String Palindrome
// https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// 730. Count Different Palindromic Subsequences
// https://leetcode.com/problems/count-different-palindromic-subsequences/
int longestPalindromeSubseq(string s) {
    int n = s.size();
    vector<int> dp(n, 0);

    for (int i = n - 1; i >= 0; --i) {
        int back_up = 0;
        for (int j = i + 1; j < n; ++j) {
            int temp = dp[j];
            if (s[i] == s[j])
                dp[j] = 2 + back_up;
            else
                dp[j] = max(dp[j], dp[j - 1]);
            back_up = temp;
        }
    }
    return dp[n - 1];
}

// Interleaving String
// LeetCode: 97. Interleaving String
// https://leetcode.com/problems/interleaving-string/
// Related:
// 72. Edit Distance
// https://leetcode.com/problems/edit-distance/
// 1143. Longest Common Subsequence
// https://leetcode.com/problems/longest-common-subsequence/
// 115. Distinct Subsequences
// https://leetcode.com/problems/distinct-subsequences/
// 583. Delete Operation for Two Strings
// https://leetcode.com/problems/delete-operation-for-two-strings/
bool isInterleave(string s1, string s2, string s3) {
    int m = s1.size(), n = s2.size();
    if (m + n != s3.size()) return false;
    
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    
    for (int j = 1; j <= n; j++) {
        dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
    }
    
    for (int i = 1; i <= m; i++) {
        dp[0] = dp[0] && s1[i - 1] == s3[i - 1];
        for (int j = 1; j <= n; j++) {
            dp[j] = (dp[j] && s1[i - 1] == s3[i + j - 1]) ||
                    (dp[j - 1] && s2[j - 1] == s3[i + j - 1]);
        }
    }
    return dp[n];
}

// Stone Game (Game Theory DP)
// LeetCode: 877. Stone Game
// https://leetcode.com/problems/stone-game/
// Related:
// 1140. Stone Game II
// https://leetcode.com/problems/stone-game-ii/
// 1406. Stone Game III
// https://leetcode.com/problems/stone-game-iii/
// 1510. Stone Game IV
// https://leetcode.com/problems/stone-game-iv/
// 1563. Stone Game V
// https://leetcode.com/problems/stone-game-v/
// 1686. Stone Game VI
// https://leetcode.com/problems/stone-game-vi/
bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    vector<int> dp(n);
    for (int i = 0; i < n; i++) dp[i] = piles[i];
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i] = max(piles[i] - dp[i + 1], piles[j] - dp[i]);
        }
    }
    return dp[0] > 0;
}

// Russian Doll Envelopes (2D LIS)
// LeetCode: 354. Russian Doll Envelopes
// https://leetcode.com/problems/russian-doll-envelopes/
// Related:
// 300. Longest Increasing Subsequence
// https://leetcode.com/problems/longest-increasing-subsequence/
// 646. Maximum Length of Pair Chain
// https://leetcode.com/problems/maximum-length-of-pair-chain/
// 435. Non-overlapping Intervals
// https://leetcode.com/problems/non-overlapping-intervals/
// 1048. Longest String Chain
// https://leetcode.com/problems/longest-string-chain/
int maxEnvelopes(vector<vector<int>>& envelopes) {
    sort(envelopes.begin(), envelopes.end(), [](const auto& a, const auto& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });
    
    vector<int> lis;
    for (auto& env : envelopes) {
        auto it = lower_bound(lis.begin(), lis.end(), env[1]);
        if (it == lis.end()) lis.push_back(env[1]);
        else *it = env[1];
    }
    return lis.size();
}

// Cherry Pickup (3D DP optimized to 2D)
// LeetCode: 741. Cherry Pickup
// https://leetcode.com/problems/cherry-pickup/
// Related:
// 1463. Cherry Pickup II
// https://leetcode.com/problems/cherry-pickup-ii/
// 64. Minimum Path Sum
// https://leetcode.com/problems/minimum-path-sum/
// 174. Dungeon Game
// https://leetcode.com/problems/dungeon-game/
// 1594. Maximum Non Negative Product in a Matrix
// https://leetcode.com/problems/maximum-non-negative-product-in-a-matrix/
int cherryPickup(vector<vector<int>>& grid) {
    int n = grid.size();
    vector<vector<int>> dp(n, vector<int>(n, -1));
    dp[0][0] = grid[0][0];
    
    for (int k = 1; k < 2 * n - 1; k++) {
        vector<vector<int>> newDp(n, vector<int>(n, -1));
        for (int i1 = max(0, k - n + 1); i1 <= min(k, n - 1); i1++) {
            for (int i2 = max(0, k - n + 1); i2 <= min(k, n - 1); i2++) {
                int j1 = k - i1, j2 = k - i2;
                if (grid[i1][j1] == -1 || grid[i2][j2] == -1) continue;
                
                int val = grid[i1][j1];
                if (i1 != i2) val += grid[i2][j2];
                
                for (int pi1 = i1 - 1; pi1 <= i1; pi1++) {
                    for (int pi2 = i2 - 1; pi2 <= i2; pi2++) {
                        int pj1 = k - 1 - pi1, pj2 = k - 1 - pi2;
                        if (pi1 >= 0 && pi2 >= 0 && pj1 >= 0 && pj2 >= 0 && 
                            dp[pi1][pi2] != -1) {
                            newDp[i1][i2] = max(newDp[i1][i2], dp[pi1][pi2] + val);
                        }
                    }
                }
            }
        }
        dp = newDp;
    }
    return max(0, dp[n - 1][n - 1]);
}