C++算法（动态规划）

1. 斐波那契数列（Fibonacci Sequence）

问题描述：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

// 方法1：递归（效率低，存在大量重复计算）
// 时间复杂度：O(2^n)，空间复杂度：O(n)
int fibonacci1(int n) {
    if (n <= 1) return n;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
}

// 方法2：记忆化搜索
// 时间复杂度：O(n)，空间复杂度：O(n)
int fibonacci2(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci2(n - 1, memo) + fibonacci2(n - 2, memo);
    return memo[n];
}

// 方法3：动态规划（自底向上）
// 时间复杂度：O(n)，空间复杂度：O(n)
int fibonacci3(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];
}

// 方法4：空间优化版本
// 时间复杂度：O(n)，空间复杂度：O(1)
int fibonacci4(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;
}

// 方法5：矩阵快速幂
// 时间复杂度：O(log n)，空间复杂度：O(1)
int fibonacci5(int n) {
    if (n <= 1) return n;
    // 使用矩阵 [[1,1],[1,0]]^n 计算
    // 实现略
}

2. 0/1 背包问题（0/1 Knapsack）

问题描述：给定 n 个物品，每个物品有重量和价值，背包容量为 W，求最大价值

// 方法1：二维 DP
// 时间复杂度：O(n*W)，空间复杂度：O(n*W)
int knapsack01_2D(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    // dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            // 不选第 i 个物品
            dp[i][w] = dp[i - 1][w];
            
            // 选第 i 个物品（如果能放下）
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i][w], 
                              dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    return dp[n][W];
}

// 方法2：一维 DP（空间优化）
// 时间复杂度：O(n*W)，空间复杂度：O(W)
int knapsack01_1D(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++) {
        // 必须从后向前遍历，避免重复使用物品
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

// 回溯找出选择的物品
vector<int> knapsackWithItems(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    // 填充 DP 表
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i][w], 
                              dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    // 回溯找出选择的物品
    vector<int> selected;
    int w = W;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            selected.push_back(i - 1);
            w -= weights[i - 1];
        }
    }
    
    return selected;
}

// 使用示例
int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int W = 8;
    cout << "最大价值: " << knapsack01_1D(weights, values, W) << endl;
}

3. 最长递增子序列（Longest Increasing Subsequence, LIS）

问题描述：找出数组中最长的严格递增子序列的长度

// 方法1：动态规划
// 时间复杂度：O(n²)，空间复杂度：O(n)
int lengthOfLIS_DP(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int n = nums.size();
    vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的 LIS 长度
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// 方法2：贪心 + 二分查找（最优解）
// 时间复杂度：O(n log n)，空间复杂度：O(n)
int lengthOfLIS_Binary(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    vector<int> tails;  // tails[i] 表示长度为 i+1 的 LIS 的最小尾部元素
    
    for (int num : nums) {
        // 二分查找第一个大于等于 num 的位置
        auto it = lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            tails.push_back(num);  // num 比所有元素都大
        } else {
            *it = num;  // 替换为更小的元素
        }
    }
    
    return tails.size();
}

// 打印 LIS（使用 DP 方法）
vector<int> printLIS(vector<int>& nums) {
    if (nums.empty()) return {};
    
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> parent(n, -1);
    int maxLen = 1, maxIndex = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIndex = i;
        }
    }
    
    // 回溯构建 LIS
    vector<int> lis;
    for (int i = maxIndex; i != -1; i = parent[i]) {
        lis.push_back(nums[i]);
    }
    reverse(lis.begin(), lis.end());
    
    return lis;
}

4. 最长公共子序列（Longest Common Subsequence, LCS）

问题描述：找出两个字符串的最长公共子序列长度

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

// 方法2：空间优化（一维 DP）
// 时间复杂度：O(m*n)，空间复杂度：O(min(m,n))
int longestCommonSubsequence_Optimized(string text1, string text2) {
    if (text1.length() < text2.length()) {
        swap(text1, text2);
    }
    
    int m = text1.length(), n = text2.length();
    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];
}

// 打印 LCS
string printLCS(string text1, string text2) {
    int m = text1.length(), n = text2.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 (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 回溯构建 LCS
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1[i - 1] == text2[j - 1]) {
            lcs = text1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs;
}

5. 最长公共子串（Longest Common Substring）

问题描述：找出两个字符串的最长公共连续子串长度

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int longestCommonSubstring(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0;
    
    // dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            }
        }
    }
    
    return maxLen;
}

// 方法2：空间优化
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int longestCommonSubstring_Optimized(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<int> dp(n + 1, 0);
    int maxLen = 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;
                maxLen = max(maxLen, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
    
    return maxLen;
}

// 打印最长公共子串
string printLongestCommonSubstring(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0, endIndex = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i - 1;
                }
            }
        }
    }
    
    return text1.substr(endIndex - maxLen + 1, maxLen);
}

6. 编辑距离（Levenshtein Distance）

问题描述：将字符串 s1 转换为 s2 所需的最少操作次数（插入、删除、替换）

// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化边界
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    // dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];  // 不需要操作
            } else {
                dp[i][j] = min({
                    dp[i - 1][j] + 1,      // 删除
                    dp[i][j - 1] + 1,      // 插入
                    dp[i - 1][j - 1] + 1   // 替换
                });
            }
        }
    }
    
    return dp[m][n];
}

// 空间优化版本
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int minDistance_Optimized(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<int> dp(n + 1);
    
    for (int j = 0; j <= n; j++) dp[j] = j;
    
    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] = min({dp[j], dp[j - 1], prev}) + 1;
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

7. 爬楼梯问题（Climbing Stairs）

问题描述：每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种方法

// 方法1：动态规划
// 时间复杂度：O(n)，空间复杂度：O(n)
int climbStairs(int n) {
    if (n <= 2) return n;
    
    vector<int> dp(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

// 方法2：空间优化
// 时间复杂度：O(n)，空间复杂度：O(1)
int climbStairs_Optimized(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;
}

// 扩展：每次可以爬 1 到 k 个台阶
int climbStairs_K(int n, int k) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j <= i; j++) {
            dp[i] += dp[i - j];
        }
    }
    
    return dp[n];
}

8. 不同路径数（Unique Paths）

问题描述：从左上角到右下角有多少条不同路径（只能向右或向下）

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 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];
}

// 方法2：一维 DP（空间优化）
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int uniquePaths_Optimized(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];
}

// 方法3：组合数学（最优解）
// 时间复杂度：O(min(m,n))，空间复杂度：O(1)
int uniquePaths_Math(int m, int n) {
    long long result = 1;
    int steps = m + n - 2;
    int down = m - 1;
    
    // 计算 C(steps, down)
    for (int i = 1; i <= down; i++) {
        result = result * (steps - down + i) / i;
    }
    
    return result;
}

// 扩展：有障碍物的情况
int uniquePathsWithObstacles(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) return 0;
    
    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = 1;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                dp[i][j] = 0;
            } else {
                if (i > 0) dp[i][j] += dp[i - 1][j];
                if (j > 0) dp[i][j] += dp[i][j - 1];
            }
        }
    }
    
    return dp[m - 1][n - 1];
}

9. 买卖股票的最佳时机（Best Time to Buy and Sell Stock）

// 问题1：只能买卖一次
// 时间复杂度：O(n)，空间复杂度：O(1)
int maxProfit_OneTransaction(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    
    return maxProfit;
}

// 问题2：可以买卖多次
// 时间复杂度：O(n)，空间复杂度：O(1)
int maxProfit_MultipleTransactions(vector<int>& prices) {
    int maxProfit = 0;
    
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i - 1]) {
            maxProfit += prices[i] - prices[i - 1];
        }
    }
    
    return maxProfit;
}

// 问题3：最多买卖 k 次
// 时间复杂度：O(n*k)，空间复杂度：O(k)
int maxProfit_KTransactions(int k, vector<int>& prices) {
    int n = prices.size();
    if (n == 0 || k == 0) return 0;
    
    // 如果 k >= n/2，相当于无限次交易
    if (k >= n / 2) {
        return maxProfit_MultipleTransactions(prices);
    }
    
    // dp[i][0] 表示第 i 次交易后不持有股票的最大利润
    // dp[i][1] 表示第 i 次交易后持有股票的最大利润
    vector<vector<int>> dp(k + 1, vector<int>(2, 0));
    
    for (int i = 1; i <= k; i++) {
        dp[i][1] = -prices[0];
    }
    
    for (int i = 1; i < n; i++) {
        for (int j = k; j >= 1; j--) {
            dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
            dp[j][1] = max(dp[j][1], dp[j - 1][0] - prices[i]);
        }
    }
    
    return dp[k][0];
}

// 问题4：有冷却期（卖出后需要冷却一天）
// 时间复杂度：O(n)，空间复杂度：O(1)
int maxProfit_WithCooldown(vector<int>& prices) {
    int n = prices.size();
    if (n <= 1) return 0;
    
    int hold = -prices[0];      // 持有股票
    int sold = 0;               // 刚卖出股票
    int rest = 0;               // 冷却期
    
    for (int i = 1; i < n; i++) {
        int prevHold = hold;
        int prevSold = sold;
        
        hold = max(hold, rest - prices[i]);
        sold = prevHold + prices[i];
        rest = max(rest, prevSold);
    }
    
    return max(sold, rest);
}

// 问题5：有手续费
// 时间复杂度：O(n)，空间复杂度：O(1)
int maxProfit_WithFee(vector<int>& prices, int fee) {
    int hold = -prices[0];
    int cash = 0;
    
    for (int i = 1; i < prices.size(); i++) {
        hold = max(hold, cash - prices[i]);
        cash = max(cash, hold + prices[i] - fee);
    }
    
    return cash;
}

10. 求解最大子数组和（Maximum Subarray Sum / Kadane's Algorithm）

int maxSubArray_Kadane(vector<int>& nums) {
    int maxSum = nums[0];      // 全局最大和
    int currentSum = nums[0];  // 当前子数组和
    
    for (int i = 1; i < nums.size(); i++) {
        // 关键：要么加上当前元素，要么从当前元素重新开始
        currentSum = max(nums[i], currentSum + nums[i]);
        
        // 更新全局最大和
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// 使用示例
int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和: " << maxSubArray_Kadane(nums) << endl;  // 输出: 6
}

11. 最小路径和（Minimum Path Sum）

问题描述：从左上角到右下角的最小路径和（只能向右或向下）

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
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];
    }
    
    // 填充 DP 表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    return dp[m - 1][n - 1];
}

// 方法2：一维 DP（空间优化）
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int minPathSum_Optimized(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n);
    
    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + grid[0][j];
    }
    
    for (int i = 1; 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];
}

// 方法3：原地修改（空间复杂度 O(1)）
int minPathSum_InPlace(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    
    for (int i = 1; i < m; i++) {
        grid[i][0] += grid[i - 1][0];
    }
    
    for (int j = 1; j < n; j++) {
        grid[0][j] += grid[0][j - 1];
    }
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
        }
    }
    
    return grid[m - 1][n - 1];
}

// 打印路径
vector<pair<int, int>> printMinPath(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] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    
    // 回溯路径
    vector<pair<int, int>> path;
    int i = m - 1, j = n - 1;
    path.push_back({i, j});
    
    while (i > 0 || j > 0) {
        if (i == 0) {
            j--;
        } else if (j == 0) {
            i--;
        } else if (dp[i - 1][j] < dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
        path.push_back({i, j});
    }
    
    reverse(path.begin(), path.end());
    return path;
}

12. 正则表达式匹配（Regular Expression Matching）

问题描述：实现支持 '.' 和 '*' 的正则表达式匹配

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的元素

// 方法1：动态规划
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
bool isMatch(string s, string p) {
    int m = s.length(), n = p.length();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    
    // 空字符串匹配空模式
    dp[0][0] = true;
    
    // 处理 a*b*c* 这种模式可以匹配空字符串
    for (int j = 2; j <= n; j++) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    // 填充 DP 表
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j - 1] == '*') {
                // '*' 匹配 0 次前面的字符
                dp[i][j] = dp[i][j - 2];
                
                // '*' 匹配 1 次或多次前面的字符
                if (p[j - 2] == s[i - 1] || p[j - 2] == '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            } else if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    return dp[m][n];
}

// 方法2：递归 + 记忆化
bool isMatch_Memo(string s, string p, int i, int j, 
                  vector<vector<int>>& memo) {
    if (j == p.length()) {
        return i == s.length();
    }
    
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    
    bool firstMatch = (i < s.length() && 
                      (p[j] == s[i] || p[j] == '.'));
    
    bool result;
    if (j + 1 < p.length() && p[j + 1] == '*') {
        // '*' 匹配 0 次或多次
        result = isMatch_Memo(s, p, i, j + 2, memo) ||
                (firstMatch && isMatch_Memo(s, p, i + 1, j, memo));
    } else {
        result = firstMatch && isMatch_Memo(s, p, i + 1, j + 1, memo);
    }
    
    memo[i][j] = result;
    return result;
}

bool isMatch_Recursive(string s, string p) {
    vector<vector<int>> memo(s.length() + 1, 
                            vector<int>(p.length() + 1, -1));
    return isMatch_Memo(s, p, 0, 0, memo);
}

// 使用示例
int main() {
    cout << isMatch("aa", "a") << endl;       // false
    cout << isMatch("aa", "a*") << endl;      // true
    cout << isMatch("ab", ".*") << endl;      // true
    cout << isMatch("aab", "c*a*b") << endl;  // true
}

13. 最大矩形问题（Maximal Rectangle）

问题描述：在二维矩阵中找到只包含 1 的最大矩形面积

// 方法1：使用柱状图最大矩形（最优解）
// 时间复杂度：O(m*n)，空间复杂度：O(n)

// 辅助函数：计算柱状图中的最大矩形
int largestRectangleInHistogram(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        
        while (!st.empty() && h < heights[st.top()]) {
            int height = heights[st.top()];
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        
        st.push(i);
    }
    
    return maxArea;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n, 0);
    int maxArea = 0;
    
    for (int i = 0; i < m; i++) {
        // 更新每列的高度
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        
        // 计算当前行的最大矩形
        maxArea = max(maxArea, largestRectangleInHistogram(heights));
    }
    
    return maxArea;
}

// 方法2：动态规划
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int maximalRectangle_DP(vector<vector<char>>& matrix) {
    if (matrix.empty() || matrix[0].empty()) return 0;
    
    int m = matrix.size(), n = matrix[0].size();
    vector<int> left(n, 0);    // 左边界
    vector<int> right(n, n);   // 右边界
    vector<int> height(n, 0);  // 高度
    int maxArea = 0;
    
    for (int i = 0; i < m; i++) {
        int curLeft = 0, curRight = n;
        
        // 更新高度
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                height[j]++;
            } else {
                height[j] = 0;
            }
        }
        
        // 更新左边界
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == '1') {
                left[j] = max(left[j], curLeft);
            } else {
                left[j] = 0;
                curLeft = j + 1;
            }
        }
        
        // 更新右边界
        for (int j = n - 1; j >= 0; j--) {
            if (matrix[i][j] == '1') {
                right[j] = min(right[j], curRight);
            } else {
                right[j] = n;
                curRight = j;
            }
        }
        
        // 计算面积
        for (int j = 0; j < n; j++) {
            maxArea = max(maxArea, (right[j] - left[j]) * height[j]);
        }
    }
    
    return maxArea;
}

// 使用示例
int main() {
    vector<vector<char>> matrix = {
        {'1', '0', '1', '0', '0'},
        {'1', '0', '1', '1', '1'},
        {'1', '1', '1', '1', '1'},
        {'1', '0', '0', '1', '0'}
    };
    cout << "最大矩形面积: " << maximalRectangle(matrix) << endl;  // 输出: 6
}

14. 柱状图中的最大矩形（Largest Rectangle in Histogram）

问题描述：给定柱状图的高度，计算最大矩形面积

// 方法1：单调栈（最优解）
// 时间复杂度：O(n)，空间复杂度：O(n)
int largestRectangleArea(vector<int>& heights) {
    stack<int> st;
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        
        while (!st.empty() && h < heights[st.top()]) {
            int height = heights[st.top()];
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;
            maxArea = max(maxArea, height * width);
        }
        
        st.push(i);
    }
    
    return maxArea;
}

// 方法2：分治法
// 时间复杂度：O(n log n)，空间复杂度：O(log n)
int largestRectangleArea_DivideConquer(vector<int>& heights, int left, int right) {
    if (left > right) return 0;
    
    // 找到最小高度的索引
    int minIndex = left;
    for (int i = left; i <= right; i++) {
        if (heights[i] < heights[minIndex]) {
            minIndex = i;
        }
    }
    
    // 计算三种情况的最大面积
    int area1 = heights[minIndex] * (right - left + 1);
    int area2 = largestRectangleArea_DivideConquer(heights, left, minIndex - 1);
    int area3 = largestRectangleArea_DivideConquer(heights, minIndex + 1, right);
    
    return max({area1, area2, area3});
}

// 方法3：暴力法（用于理解）
// 时间复杂度：O(n²)，空间复杂度：O(1)
int largestRectangleArea_Brute(vector<int>& heights) {
    int maxArea = 0;
    int n = heights.size();
    
    for (int i = 0; i < n; i++) {
        int minHeight = heights[i];
        for (int j = i; j < n; j++) {
            minHeight = min(minHeight, heights[j]);
            maxArea = max(maxArea, minHeight * (j - i + 1));
        }
    }
    
    return maxArea;
}

// 使用示例
int main() {
    vector<int> heights = {2, 1, 5, 6, 2, 3};
    cout << "最大矩形面积: " << largestRectangleArea(heights) << endl;  // 输出: 10
}