1.1 爬楼梯

由前几个状态转移到现在这个状态

动态规划入门：从记忆化搜索到递推哔哩哔哩bilibili

70. 爬楼梯 - 力扣（LeetCode）

class Solution {
public:
    int climbStairs(int n) {
        int f0 = 0, f1 = 1;
        for (int i = 0; i < n; i++) {
            int new_f = f0 + f1;
            f0 = f1, f1 = new_f;
        }
        return f1;
    }
};

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

class Solution {// 1、记忆化搜索
public:
    int minCostClimbingStairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n + 1, -1);
        function<int(int)> dp = [&](int i) -> int {// dp(i)的含义是，到达第 i 级台阶需要的最小费用
            if (i <= 1)// 注意这里填1，因为再往下，nums 数组就越界了
                return 0;
            if (memo[i] != -1)
                return memo[i];
            memo[i] = min(dp(i - 1) + nums[i - 1], dp(i - 2) + nums[i - 2]);
            return memo[i];
        };
        return dp(n);
    }
};  

class Solution {// 2、递推
public:
    int minCostClimbingStairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; i++) 
            dp[i] = min(dp[i - 1] + nums[i - 1], dp[i - 2] + nums[i - 2]);
        return dp[n];
    }
};

class Solution {// 3、递推（空间优化版）
public:
    int minCostClimbingStairs(vector<int>& nums) {
        int n = nums.size();
        int f0 = 0, f1 = 0;
        for (int i = 1; i < n; i++) {
            int new_f = min(f0 + nums[i - 1], f1 + nums[i]);
            f0 = f1;
            f1 = new_f;
        }
        return f1;
    }
};

377. 组合总和 Ⅳ - 力扣（LeetCode）

本质上是爬楼梯，每一个状态根据数组长度个状态转移而来

class Solution { // 1、记忆化搜索
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> memo(target + 1, -1);
        function<int(int)> dp = [&](int i) -> int {
            if (i == 0)
                return 1;
            if (memo[i] != -1) // 如果设置为0，会导致无限循环
                return memo[i];
            memo[i] = 0;
            for (int x : nums)
                if (x <= i)
                    memo[i] += dp(i - x);
            return memo[i];
        };
        return dp(target);
    }
};

class Solution {// 2、递推
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        vector<unsigned> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int x : nums)
                if (x <= i)
                    dp[i] += dp[i - x];
        }
        return dp[target];
    }
};

2466. 统计构造好字符串的方案数 - 力扣（LeetCode）

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;
        const int MOD = 1000000007;
        for (int i = 0; i <= high; i++) {
            if (i >= zero)
                dp[i] = dp[i - zero];
            if (i >= one)
                dp[i] = (dp[i] + dp[i - one]) % MOD;
        }

        int ans = 0;
        for (int i = low; i <= high; i++) {
            ans += dp[i];
            ans %= MOD;
        }

        return ans;
    }
};

2266. 统计打字方案数 - 力扣（LeetCode）

class Solution {
public:
    int countTexts(string pressedKeys) {
        vector<pair<char, int>> nums;
        char c = pressedKeys[0];
        int cnt = 0;
        for (int i = 0; i < pressedKeys.size(); i++) {
            if (c == pressedKeys[i])
                ++cnt;
            else {
                nums.push_back({c, cnt});
                cnt = 1;
                c = pressedKeys[i];
            }
        }
        nums.push_back({c, cnt});

        const unsigned long long MOD = 1000000007;
        vector<unsigned long long> dp1(100001), dp2(100001);
        dp1[1] = 1, dp1[2] = 2, dp1[3] = 4, dp1[4] = 7;
        dp2[1] = 1, dp2[2] = 2, dp2[3] = 4, dp2[4] = 8;
        for (size_t i = 5; i <= 100000; i++) {
            dp1[i] = (dp1[i - 1] + dp1[i - 2] + dp1[i - 3]) % MOD;
            dp2[i] = (dp2[i - 1] + dp2[i - 2] + dp2[i - 3] + dp2[i - 4]) % MOD;
        }

        unsigned long long ans = 1;
        for (auto it : nums) {
            if (it.first != '7' && it.first != '9')
                ans *= dp1[it.second];
            else
                ans *= dp2[it.second];
            ans %= MOD;
        }
        return ans;
    }
};

---

1.2 打家劫舍

选了这一个，就不能选下一个（下几个）

198. 打家劫舍 - 力扣（LeetCode）

class Solution {// 1、记忆化搜索
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> memo(n, -1);// 辅助数组，实现记忆化搜索
        function<int(int)> dp = [&](int i) -> int {
            if (i < 0)
                return 0;
            if (memo[i] != -1)
                return memo[i];
            memo[i] = max(dp(i - 1), dp(i - 2) + nums[i]);
            return memo[i];
        };
        return dp(n - 1);
    }
};

class Solution {// 2、递推
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < n; i++)
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);// 核心代码部分，递推和记忆化搜索是非常相似的
        return dp[n - 1];
    }
};

class Solution {// 3、递推（空间优化版）
public:
    int rob(vector<int>& nums) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            int new_f = max(f0 + x, f1);
            f0 = f1;// 注意这两句的顺序不能反了！
            f1 = new_f;// 注意这两句的顺序不能反了！
        }
        return f1;
    }
};

740. 删除并获得点数 - 力扣（LeetCode）

这个解法模板可以解决这个问题，但是sum元素上溢的话，就得增大数据类型，或者使用pair

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int maxval = ranges::max(nums);
        vector<int> sum(maxval + 1, 0);
        for (int val : nums)
            sum[val] += val;

        int f0 = 0, f1 = 0;
        for (int i = 0; i < maxval + 1; i++) {
            int new_f = max(f0 + sum[i], f1);
            f0 = f1, f1 = new_f;
        }
        return f1;
    }
};

2320. 统计放置房子的方式数 - 力扣（LeetCode）

class Solution {
public:
    int countHousePlacements(int n) {
        if (n == 1)
            return 4;
        vector<long long> dp(n+1, 0);
        dp[0] = 1, dp[1] = 2;
        for (int i = 2; i <= n; ++i)
            dp[i] = (dp[i - 1] + dp[i - 2])%1000000007;
        return (dp[n] * dp[n]) % 1000000007;
    }
};

213. 打家劫舍 II - 力扣（LeetCode）

连起来的时候，分类讨论即可

class Solution {
public:
    int rob(vector<int>& nums) {
        int f0 = 0, f1 = 0, n = nums.size();
        if (n < 2)
            return nums[0];
        for (int i = 0; i < n - 1; i++) {
            int new_f = max(f0 + nums[i], f1);
            f0 = f1, f1 = new_f;
        }
        int ans = f1;
        f0 = 0, f1 = 0;
        for (int i = 1; i < n; i++) {
            int new_f = max(f0 + nums[i], f1);
            f0 = f1, f1 = new_f;
        }
        return max(ans, f1);
    }
};

3186. 施咒的最大总伤害 - 力扣（LeetCode）

这题和740类似，但是数据上溢了，只能用pair表示元素

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        // 爆内存了
        // int maxval = ranges::max(power);
        // vector<int> sum(maxval + 1);
        // for (int val : power)
        //     sum[val] += val;

        // vector<int> dp(maxval + 1, 0);
        // int f0 = 0, f1 = 0, f2 = 0;
        // for (int i = 0; i <= maxval; i++) {
        //     int new_f = max(max(f0 + sum[i], f1), f2);
        //     f0 = f1;
        //     f1 = f2;
        //     f2 = new_f;
        // }
        // return f2;

        unordered_map<int, int> map;
        for (auto x : power)
            ++map[x];
        vector<pair<int, int>> nums(map.begin(), map.end());
        ranges::sort(nums);
        int n = nums.size();
        vector<long long> dp(n + 1);
        for (int i = 0, j = 0; i < n; i++) {
            auto& [x, c] = nums[i];
            while (nums[j].first < x - 2)
                ++j;
            dp[i + 1] = max(dp[i], dp[j] + (long long)x * c);
        }
        return dp[n];
    }
};

---

1.3 最大子数组和

遍历数组，记录 max_f 和 min_f

53. 最大子数组和 - 力扣（LeetCode）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN, sum = 0;// 由于题目要求子数组非空，因此ans初始化为INT_MIN，如果没有这个要求，应该初始化为0
        for (int x : nums) {
            sum = max(sum, 0) + x;
            ans = max(ans, sum);
        }
        return ans;
    }
};

2606. 找到最大开销的子字符串 - 力扣（LeetCode）

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        unordered_map<char, int> map;
        for (int i = 0; i < chars.size(); i++)
            map.emplace(chars[i], vals[i]);
        for (int i = 0; i < 26; i++)
            if (map.find('a' + i) == map.end())
                map.emplace('a' + i, i + 1);
        int ans = 0, sum = 0, n = s.size();
        for (int left = 0, right = 0; right < n; right++) {
            while (sum < 0) {
                sum -= map[s[left]];
                ++left;
            }
            sum += map[s[right]];
            ans = max(ans, sum);
        }
        return ans;
    }
};

1749. 任意子数组和的绝对值的最大值 - 力扣（LeetCode）

class Solution {
public:
    int maxAbsoluteSum(vector<int>& nums) {
        int ans = 0, f_max = 0, f_min = 0;
        for (int x : nums) {
            f_max = max(f_max, 0) + x;
            f_min = min(f_min, 0) + x;
            ans = max(ans, max(f_max, -f_min));
        }
        return ans;
    }
};

1191. K 次串联后最大子数组之和 - 力扣（LeetCode）

分 k==1 和 k>1 讨论。

class Solution {
public:
    int kConcatenationMaxSum(vector<int>& nums, int k) {
        int mod = 1e9 + 7;
        if (k == 1) {
            int ans = 0, f_max = 0;
            for (int x : nums) {
                f_max = max(f_max, 0) + x;
                ans = max(ans, f_max);
            }
            return ans;
        } else {
            int ans = 0, f_max = 0, n = nums.size(), sum = 0;
            for (int j = 0; j < 2; j++) {
                for (int i = 0; i < n; i++) {
                    sum += nums[i];
                    f_max = max(f_max, 0) + nums[i];
                    ans = max(ans, f_max);
                }
            }
            sum /= 2;
            if (sum > 0)
                ans = (ans + (long long)(k - 2) * sum) % mod;
            return ans % mod;
        }
    }
};

918. 环形子数组的最大和 - 力扣（LeetCode）

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int sum = 0, max_f = 0, min_f = 0, max_s = INT_MIN, min_s = 0; // 由于要求不为空，因此max_s不能初始化为0，而min_s可以初始化为0
        for (int x : nums) {
            sum += x;
            max_f = max(max_f, 0) + x;
            min_f = min(min_f, 0) + x;
            max_s = max(max_s, max_f);
            min_s = min(min_s, min_f);
        }
        return min_s == sum ? max_s : max(max_s, sum - min_s);
    }
};

2321. 拼接数组的最大分数 - 力扣（LeetCode）

class Solution {
public:
    int slove(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), res = 0, max_f = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += nums2[i];
            max_f = max(max_f, 0) + nums1[i] - nums2[i];
            res = max(res, max_f);
        }
        return sum + res;
    }
    int maximumsSplicedArray(vector<int>& nums1, vector<int>& nums2) {
        return max(slove(nums1, nums2), slove(nums2, nums1));
    }
};

152. 乘积最大子数组 - 力扣（LeetCode）

也可以记录 max_f, min_f

class Solution {// 正向乘一遍，再逆向乘一遍
public:
    int maxProduct(vector<int>& nums) {
        int product = 1, n = nums.size(), ans = INT_MIN;
        for (int i = 0; i < n; i++) {
            product *= nums[i];
            ans = max(ans, product);
            if (product == 0)
                product = 1;
        }
        product = 1;
        for (int i = n - 1; i >= 0; i--) {
            product *= nums[i];
            ans = max(ans, product);
            if (product == 0)
                product = 1;
        }
        return ans;
    }
};

---

2.1 网格图DP

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& dp) {
        int n = dp.size(), m = dp[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j > 0)
                    dp[i][j] += dp[i][j - 1];
                if (i > 0 && j == 0)
                    dp[i][j] += dp[i - 1][j];
                if (i > 0 && j > 0)
                    dp[i][j] += max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[n - 1][m - 1];
    }
};

62. 不同路径 - 力扣（LeetCode）

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> matrix(m + 1, vector<int>(n + 1, 0));
        matrix[0][1] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i + 1][j + 1] = matrix[i + 1][j] + matrix[i][j + 1];
            }
        }
        return matrix[m][n];
    }
};

63. 不同路径 II - 力扣（LeetCode）

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        int m = obstacleGrid.size(), n = obstacleGrid[0].size();
        int dp[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            if (obstacleGrid[i][0] == 1)
                dp[i][0] = 0;
            else
                dp[i][0] = dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            if (obstacleGrid[0][i] == 1)
                dp[0][i] = 0;
            else
                dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

64. 最小路径和 - 力扣（LeetCode）

class Solution {
public:
    int minPathSum(vector<vector<int>>& nums) {
        int m = nums.size(), n = nums[0].size();
        for (int i = 1; i < n; i++)
            nums[0][i] += nums[0][i - 1];
        for (int i = 1; i < m; i++)
            nums[i][0] += nums[i - 1][0];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
                nums[i][j] += min(nums[i - 1][j], nums[i][j - 1]);
        }
        return nums[m - 1][n - 1];
    }
};

120. 三角形最小路径和 - 力扣（LeetCode）

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = 0; i < triangle.size() - 1; i++) {
            triangle[i + 1][0] += triangle[i][0];
            for (int j = 1; j < triangle[i].size(); j++) 
                triangle[i + 1][j] += min(triangle[i][j - 1], triangle[i][j]);
            triangle[i + 1][triangle[i].size()] += triangle[i][triangle[i].size() - 1];
        }
        int ans = 10010;
        for (int i = 0; i < triangle[triangle.size() - 1].size(); i++)
            ans = min(ans, triangle[triangle.size() - 1][i]);
        return ans;
    }
};

931. 下降路径最小和 - 力扣（LeetCode）

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 1)
            return matrix[0][0];
        for (int i = 1; i < n; i++) {
            matrix[i][0] += min(matrix[i - 1][0], matrix[i - 1][1]);
            for (int j = 1; j < n - 1; ++j)
                matrix[i][j] +=
                    min(min(matrix[i - 1][j - 1], matrix[i - 1][j]),
                        min(matrix[i - 1][j], matrix[i - 1][j + 1]));
            matrix[i][n - 1] += min(matrix[i - 1][n - 2], matrix[i - 1][n - 1]);
        }
        return *min_element(matrix[n - 1].begin(), matrix[n - 1].end());
    }
};

1289. 下降路径最小和 II - 力扣（LeetCode）

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = 20000;
                for (int k = 0; k < n; k++)
                    if (k != j)
                        temp = min(temp, grid[i - 1][k]);
                grid[i][j] += temp;
            }
        }
        return *min_element(grid[n - 1].begin(), grid[n - 1].end());
    }
};

2684. 矩阵中移动的最大次数 - 力扣（LeetCode）

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        function<void(int, int)> dfs = [&](int i, int j) {
            ans = max(ans, j);
            if (ans == n - 1)
                return;
            for (int x = max(0, i - 1); x < min(m, i + 2); x++) {// 注意这里防止下标出界的处理，可以学习
                if (grid[i][j] < grid[x][j + 1])
                    dfs(x, j + 1);
            }
            grid[i][j] = 0;
        };
        for (int i = 0; i < m; i++)
            dfs(i, 0);
        return ans;
    }
};

---

2.2 网格图DP进阶

1594. 矩阵的最大非负积 - 力扣（LeetCode）

class Solution {// 仍然是记录max与min
public:
    int maxProductPath(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int mod = 1e9 + 7;
        vector<vector<long long>> max_matrix(m, vector<long long>(n));
        vector<vector<long long>> min_matrix(m, vector<long long>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max_matrix[i][j] = grid[i][j];
                min_matrix[i][j] = grid[i][j];
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j > 0)
                    min_matrix[i][j] = max_matrix[i][j] =
                        max_matrix[i][j - 1] * grid[i][j];
                if (i > 0 && j == 0)
                    min_matrix[i][j] = max_matrix[i][j] =
                        max_matrix[i - 1][j] * grid[i][j];
                if (i > 0 && j > 0) {
                    if (grid[i][j] >= 0) {
                        max_matrix[i][j] =
                            max(max_matrix[i - 1][j], max_matrix[i][j - 1]) *
                            grid[i][j];
                        min_matrix[i][j] =
                            min(min_matrix[i - 1][j], min_matrix[i][j - 1]) *
                            grid[i][j];
                    } else {
                        max_matrix[i][j] =
                            min(min_matrix[i - 1][j], min_matrix[i][j - 1]) *
                            grid[i][j];
                        min_matrix[i][j] =
                            max(max_matrix[i - 1][j], max_matrix[i][j - 1]) *
                            grid[i][j];
                    }
                }
            }
        }
        return max_matrix[m - 1][n - 1] < 0 ? -1
                                            : max_matrix[m - 1][n - 1] % mod;
    }
};

1301. 最大得分的路径数目 - 力扣（LeetCode）

class Solution {
public:
    int mod = 1e9 + 7;
    int n;
    void update(vector<vector<pair<int, int>>>& dp, int x, int y, int u,
                int v) {
        if (u >= n || v >= n || dp[u][v].first == -1)
            return;
        if (dp[u][v].first > dp[x][y].first)
            dp[x][y] = dp[u][v];// 更大，则更新
        else if (dp[u][v].first == dp[x][y].first) {
            dp[x][y].second += dp[u][v].second;// 加法原理
            dp[x][y].second %= mod;
        }
    }
    vector<int> pathsWithMaxScore(vector<string>& board) {
        this->n = board.size();
        vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n, {-1, 0}));
        dp[n - 1][n - 1] = {0, 1};
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (!(i == n - 1 && j == n - 1) && board[i][j] != 'X') {
                    update(dp, i, j, i + 1, j);
                    update(dp, i, j, i, j + 1);
                    update(dp, i, j, i + 1, j + 1);
                    if (dp[i][j].first != -1)
                        dp[i][j].first += (board[i][j] == 'E' ? 0 : board[i][j] - '0');
                }
            }
        }
        return dp[0][0].first == -1 ? vector<int>{0, 0} : vector<int>{dp[0][0].first, dp[0][0].second};
    }
};

2435. 矩阵中和能被 K 整除的路径 - 力扣（LeetCode）

class Solution {// 将dp元素初始化为一个vector，存放各个结果的方案数
public:
    int mod = 1e9 + 7;
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<vector<int>>> dp( m + 1, vector<vector<int>>(n + 1, vector<int>(k, 0)));
        dp[0][1][0] = 1;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                for (int v = 0; v < k; v++)
                    dp[i + 1][j + 1][(v + grid[i][j]) % k] =
                        (dp[i + 1][j][v] + dp[i][j + 1][v]) % mod;
        return dp[m][n][0] % mod;
    }
};

174. 地下城游戏 - 力扣（LeetCode）

// 正向思考的话，考虑dp[i][j]为到达(i,j)时的血量，这样的话存在一个问题：有两条路线，一条使你到达(i,j)时血量更高，但历史最低血量更低，也就是出发时所需的初始血量更高，另一条则相反。选择哪一条路线会因为后面的值而难以确定。
// 逆向思考的话，dp[i][j]为到达右下角所需要的最低血量，这样就避免了正向思考时的问题
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[m - 1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int minn = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(minn - dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

329. 矩阵中的最长递增路径 - 力扣（LeetCode）

class Solution {
public:
    int ans = 0;
    int m, n;
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, vector<vector<bool>>& vis, int i, int j) {
        if(vis[i][j])
            return dp[i][j];
        vis[i][j] = true;
        int up = (i == 0 || matrix[i - 1][j] <= matrix[i][j]) ? 0 : dfs(matrix, dp, vis, i - 1, j);
        int down = (i == m - 1 || matrix[i + 1][j] <= matrix[i][j]) ? 0 : dfs(matrix, dp, vis, i + 1, j);
        int left = (j == 0 || matrix[i][j - 1] <= matrix[i][j]) ? 0 : dfs(matrix, dp, vis, i, j - 1);
        int right = (j == n - 1 || matrix[i][j + 1] <= matrix[i][j]) ? 0 : dfs(matrix, dp, vis, i, j + 1);
        dp[i][j] += max(max(up, down), max(left, right));
        ans = max(ans, dp[i][j]);
        return dp[i][j];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        this->m = matrix.size(), this->n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 1));
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j])
                    continue;
                dfs(matrix, dp, vis, i, j);
            }
        }
        return ans;
    }
};

2328. 网格图中递增路径的数目 - 力扣（LeetCode）

class Solution {
public:
    int ans = 0, mod = 1e9 + 7;
    int m, n;
    vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int dfs(vector<vector<int>>& grid, vector<vector<int>>& dp, vector<vector<bool>>& vis, int i, int j) {
        if (vis[i][j])// 检查是否已经计算过
            return dp[i][j];
        vis[i][j] = true;// 置为已计算过
        for (int k = 0; k < 4; k++) {// 向四个方向DFS
            int x = i + dir[k][0], y = j + dir[k][1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y])
                dp[i][j] += dfs(grid, dp, vis, x, y);
        }
        dp[i][j] %= mod;
        ans += dp[i][j];// 累加到ans中
        ans %= mod;
        return dp[i][j];
    }
    int countPaths(vector<vector<int>>& grid) {
        this->m = grid.size(), this->n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 1));
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (vis[i][j])
                    continue;
                dfs(grid, dp, vis, i, j);
            }
        }
        return ans;
    }
};

2267. 检查是否有合法括号字符串路径 - 力扣（LeetCode）

// 设计一个变量c为进入格子之前，左括号减去右括号的数量
class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        if ((m + n) % 2 == 0 || grid[0][0] == ')' || grid[m - 1][n - 1] == '(')// 如果长度为奇数，或者左上角不是'('，右下角不是')'
            return false;
        bool vis[m][n][(m + n + 1) / 2];// 标记数组
        memset(vis, false, sizeof(vis));
        function<bool(int, int, int)> dfs = [&](int x, int y, int c) -> bool {
            if (c > m - x + n - y - 1)// 如果此时序列中'('太多，就算剩下的都是')'也无法全部匹配
                return false;
            if (x == m - 1 && y == n - 1)// 已到达右下角，由于lambda函数外面已经排除了右下角不是')'这种情况，所以这里只需要判断c == 1
                return c == 1;
            if (vis[x][y][c])// 如果访问过了，说明上次访问没有成功跳出，那么这个格子是不会成功的
                return false;
            vis[x][y][c] = true;// 标记已经访问过
            c += grid[x][y] == '(' ? 1 : -1;// 更新c
            return c >= 0 && (x < m - 1 && dfs(x + 1, y, c) || y < n - 1 && dfs(x, y + 1, c));// 
        };
        return dfs(0, 0, 0);
    }
};