动态规划入门

例1：最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

【解法1】：

[解析]：对于每一位数字，都有选和不选两种抉择。用 $dp[i]$ 表示以 $nums[i]$ 结尾的连续子数组的最大和。

如果数组的数都是正数，对于第 $i$ 个数，很明显有：$dp[i]=dp[i-1]+nums[i],\quad (i>0)$，这里的 $dp[i-1]$ 恒大于 0。

当 $dp[i-1]<0$ 时，很明显 $dp[i]=nums[i]$，即重新计算最大子数组和，因为 $dp[i-1]$ 已经产生了负收益。

初始时 $dp[0]=nums[0]$，最终数组中最大子数组和为 $dp[i]$ 中的最大值。

代码 
1
2
3
4
5
6
7
8
9

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(nums[i], dp[i-1] + nums[i]);
    }
    return *max_element(dp.begin(), dp.end());
}

【解法2】：

从解法1的动态规划方程可以看出，$dp[i]$ 仅与 $dp[i-1]$ 相关，所以我们可以利用滚动数组的思想继续优化时间复杂度。

代码 
1
2
3
4
5
6
7
8

int maxSubArray(vector<int>& nums) {
    int currmax = 0, res = nums[0];
    for (int x : nums) {
        currmax = max(currmax + x, x);
        res = max(res, currmax);
    }
    return res;
}

二维动态规划

例1：滑雪/矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

matrix example: result is 4

[解析]：我们用 $dp[i][j]$ 表示 $matrix$ 中以 $matrix[i][j]$ 为起点的最长递增路径，$dp[i][j]$ 初始为1，表示每个位置至少是长度为1的递增路径。 设 $(i^{’},j^{’})$ 为 $(i,j)$ 周围的某一点，则状态转移方程为：$$dp[i][j]=max(dp[i][j],\ dp[i^{’}][j^{’}]+1),\quad if \ matrix[i^{’}][j^{’}]<matrix[i][j]$$

需要注意的是，更新 $dp[i][j]$ 时是从高度更小的 $dp[i^{’}][j^{’}]$ 转移过来的，所以为了保证我们更新 $dp[i][j]$ 时 $dp[i^{’}][j^{’}]$ 已经准备好，我们需要新建一个 $M[m*n]$ 存储 $matrix$ 矩阵，并且按照高度对 $M$ 从小到大排序，按照排序后的 $M$ 数组的顺序更新 $dp[i][j]$。

时间复杂度取决于排序操作，为 $O(nm\log(nm))$。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
public:
    int n, m, dp[202][202];  // dp[i][j] 表示 matrix[i][j] 位置的最长递增路径
    vector<tuple<int, int, int>> M;  // 矩阵的位置和高度
    int d[5] = {-1, 0, 1, 0, -1};
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        n = matrix.size(), m = matrix[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                M.emplace_back(make_tuple(i, j, matrix[i][j]));
                dp[i][j] = 1;
            }
        }
        sort(M.begin(), M.end(), [&](auto &x, auto &y){
            auto &&[i1, j1, k1] = x;
            auto &&[i2, j2, k2] = y;
            return k1 < k2;
        });
        for (int i = 0; i < n*m; i++) {
            auto [x, y, z] = M[i];
            for (int j = 0; j < 4; j++) {
                // 比较周围的四个方向的点(x',y')，判断(x',y')的高度是否更小并且dp[x'][y']+1是否比dp[x][y]更大
                int nx = x + d[j], ny = y + d[j+1];  
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && matrix[nx][ny] < z) 
                    dp[x][y] = max(dp[x][y], dp[nx][ny] + 1);
            }
        }
        int res = INT_MIN;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

该题更推荐使用记忆化搜索的解法。

路径问题