【动态规划】（四）线性动态规划之矩阵和无串问题

1 矩阵问题

除了数组和字符串外，矩阵也是一种线性结构，很多一维数组或字符串的问题可以推广到二维，因此矩阵上也有一些经典的动态规划问题，矩阵上的动态规划问题，基本的状态设计就是用二维变量 (i, j) 共同表示以 (0, 0) 为左上角，(i, j) 为右下角的子问题。因此矩阵问题的状态定义和双串 $dp[i][j]$ 类似，状态的推导方向以及推导公式与双串相同，但是物理意义不一样，且求解时所需的子问题的变化相对更多。

三角形最小路径和

问题描述：

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

题目中都写出来状态该如何转移了，这里就不赘述了，主要讲一下优化的思路。先观察正常思路的代码：

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

可以看出 $dp[i][j]$ 只与 $dp[i-1][j]$ 和 $dp[i-1][j-1]$ 有关，因此可以利用滚动数组优化，我们只需要一个 n 大小的数组，n是三角形的层数，然后一定需要一个变量记录 $dp[i-1][j-1]$，每次$dp[j]$更新时， $dp[i-1][j]$ 就是当前的更新的位置$dp[j]$，同时需要把没更新之前的$dp[j]$记下来，作为下一次更新时的 $dp[i-1][j-1]$。对于两个特殊位置：每一次层的开头要直接把 $dp[j]$ 记下来作为下一次的$dp[i-1][j-1]$；每一层的结尾不需要记录任何数直接更新即可。优化后的代码：

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> dp(n);
        dp[0] = triangle[0][0];
        int last = dp[0];   //记录dp[i-1][j-1]
        for(int i = 1; i < n; ++i) 
        {
            for(int j = 0; j < triangle[i].size(); ++j)
            { 
                if(j == i)
                {
                    dp[j] = triangle[i][j] + last;
                }
                else if(j == 0) 
                {
                    last = dp[j];
                    dp[j] = triangle[i][j] + dp[j];
                }
                else if(j > 0)
                {
                    int temp = dp[j];
                    dp[j] =  triangle[i][j] + min(dp[j], last);
                    last = temp;
                }
            }
        }
        return *min_element(dp.begin(), dp.end());
    }
};

下降路径最小和

问题描述：

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

类似于三角路经最小和，思路不赘述。下降路径最小和 II是本题的进阶版本，难度不大，但优化起来比较困难，可以了解。

优化时的细节：可以申请数组长度为n+2，这样可以免去边界的判断，同时要注意变量的更新顺序。优化后的代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> dp(n+2, 0);	//第一层全初始化为0
        for(int i = 1; i <= n; ++i)
        {
            //从第二层开始辅助位置都要设为最大值，不能还是0了
            if(i > 1) dp[0] = dp[n+1] = INT_MAX;
            //每一层起始记录dp[i-1][j-1]、dp[i-1][j]、dp[i-1][j+1]
            int left = dp[0], mid = dp[1], right = dp[2];
            for(int j = 1; j <= n; ++j)
            {
                //之后每次更新，dp[i-1][j+1]就是dp[j+1]
                right = dp[j+1];
                int choose = min(left, min(mid, right));
                dp[j] = matrix[i-1][j-1] + choose;
                //当前的mid是下一个位置的left，当前的right是下个位置的mid
                left = mid;
                mid = right;
            }
        }
        //返回时注意不要包含辅助的位置，取中间n个数求最小值
        return *min_element(dp.begin()+1, dp.end()-1);
    }
};

最小路径和

问题描述：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

最经典的矩阵动态规划问题，难度不大，直接给出优化后的代码：

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

地下城游戏

问题描述：

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

这是一道非常巧妙的题。按照最小路径和的思路我们定义状态 $dp[i][j]$ 表示从左上角到 $(i,j)$ 所需的最低初始生命，初始值为1，至少要有1点初始生命，之后每到一个格子只要用$dp[i-1][j]$和$dp[i][j-1]$中的最小值减去当前格子的值就可以，这个思路对于一般情况似乎没什么问题，但是如果我们在某一个格子恢复了大量生命，减去当前的格子的值再取最小那么当前格子的状态$dp[i][j]$就会是负数，这不符合我们的状态定义，这说明我们要么状态转移错了，要么状态定义错了。

显然按照上面的状态定义，我们的状态转移没有问题，但是计算出的值不对，说明我们的状态定义有问题。这是因为在这个问题中我们不止要考虑每一个格子上原问题的解（最低初始生命），还要考虑我们走到这个格子的时候的当前生命值，也就是路径总和，回复大量生命值的时候我们的初始最低生命还是那么多，但是当前生命值增加了，意味着下一个格子我们可能不需要增加初始最低生命就可以到达，但是按照上面的状态定义，我们无法同时考虑初始最低生命和当前生命值，也就无法向下一状态正确传递信息。

上面的解释比较抽象，下面我们举个例子来说明，就用题目的示例：

如果按照上面的状态定义，当我们到左下角 10 这个格子的时候，这个格子的状态 $dp[2][0] = 8 - 10=-2$，那么下一次到 30 格子的时候就会变成 -32，最终到达右下角的时候最低初始生命就会是-27，显然是不合理的。正确的情况是到达左下角格子 10 的时候虽然恢复了很多生命值，但是我们想要到达这里也至少还是需要8点初始生命值，那如果直接传递 8 这个状态，到右下角的时候通过-2、-5、10、30这条路径的最低初始生命值就是 8 - (-5) = 13，依然是错误的，通过这条路径到达 右下角所需的初始最低生命就应该是8.

因此这样的状态定义是不对的，无法正确传递有效信息，这是因为有两个同样重要的参数在影响后一步的选择：一个是最低初始生命，一个是当前生命（路径总和），而这不符合动态规划的无后效性，因此不能使用这样的状态定义。

那如果改变一下定义，状态 $dp[i][j]$ 表示从 $(i,j)$ 到右下角所需的最低初始生命，我们从终点往起点推，这时我们的每一步都已经保证能到达终点，也就不需要考虑当前生命值了，只要关注从当前位置到终点的最低初始生命值即可。这时当我们再遇到回复大量生命值的格子，计算出的值是负的，这说明从这个格子到终点的生命值已经足够多了，只要我们在这个格子的时候是活着的（生命值为1）就能到达终点，因此直接将当前各自状态置 1 即可。

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int n = dungeon.size(), m = dungeon[0].size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));
        dp[n][m - 1] = dp[n - 1][m] = 1;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = m - 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];
    }
};

在上一节双串问题中，状态 $dp[i][j]$ 无论表示从 0 到 i 和 j 的状态还是表示从 i 和 j 到 n - 1 的状态，都可以得出答案，但通过这道题我们发现，有时这两种状态定义并不等价，当从前往后推导无法解决问题时，可以试试从后向前推导。

统计全为 1 的正方形子矩阵

题目描述：
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

我们用 $dp[i][j]$ 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值，假设这个值为 a ，同时这个值也是以 (i, j) 为右下角，且只包含 1 的正方形的个数（边长为1，2，…，a）的正方形各一个。因此算出所有 $dp[i][j]$ 后累加起来就是全部子矩阵个数。

那么如何计算 $dp[i][j]$ 中的每个元素值呢？对于每个位置 (i, j)，检查在矩阵中该位置的值：

• 如果该位置的值是 0，则 $dp[i][j]=0$，因为当前位置不可能在由 1 组成的正方形中；

• 如果该位置的值是 1，则 $dp[i][j]$ 的值由其上方、左方和左上方的三个相邻位置的 $dp$ 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：
  $$
  dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
  $$

关于这个状态转移方程的推导和证明比较复杂，可以参考统计全为 1 的正方形子矩阵官方题解。

边界条件，如果 i 和 j 中至少有一个为 0，则以位置 (i, j) 为右下角的最大正方形的边长只能是 1。

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> f(m, vector<int>(n));
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || j == 0) {
                    f[i][j] = matrix[i][j];
                }
                else if (matrix[i][j] == 0) {
                    f[i][j] = 0;
                }
                else {
                    f[i][j] = min(min(f[i][j - 1], f[i - 1][j]), f[i - 1][j - 1]) + 1;
                }
                ans += f[i][j];
            }
        }
        return ans;
    }
};

最大正方形

问题描述：

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 的最大面积。

这是上一题的简化版，直接给出代码：

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int ans = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(i == 0 || j == 0)
                {
                    dp[i][j] = matrix[i][j] - '0';
                }
                else if(matrix[i][j] == '0') 
                {
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;
                }
                ans = max(ans, dp[i][j]);
            }
        }
        return ans * ans;
    }
};

2 无串线性问题

线性动态规划有一类问题是没有显式的数组或字符串的。但在计算中依然可以分成若干子问题，且有动态规划的三条性质。因此也可以用动态规划来解。

只有两个键的键盘

其实是质因数分解，用动态规划也不难，但需要额外空间。

丑数 II

比较奇特的动态规划，很巧妙。也可以用优先队列（堆）去做，但空间复杂度更高

完全平方数

之前用广搜做过，但广搜太暴力，空间复杂度也高，这次试试动态规划，实际上核心思路和广搜一样。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        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];
    }
};

整数拆分

和完全平方数思路差不多，转移时要考虑的情况稍微复杂一点。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        for(int i = 2; i <= n; ++i)
        {
            for(int j = 1; j < i; ++j)
            {
                dp[i] = max(dp[i], max(dp[j] * (i - j), j * (i - j)));
            }
        }
        return dp[n];
    }
};

当然这是最直观暴力的动态规划做法，还有进一步优化的空间，以及时空复杂度都只需要 O(1) 的数学方法，具体可看官方题解。

3 线性动态规划总结

到此为止线性动态规划的几大类就都整理完了，线性动态规划是动态规划中最基础的一类，它的状态一般物理意义很明确，易于分析。在初学动态规划时，通过线性动态规划的大量练习，可以不断加深动态规划的概念理解，例如动态规划中最重要的三个概念：最优子结构，重复子问题，无后效性。下面对动态规划的三个基本概念做个简要回顾，在线性动态规划的题目练习中可以不断地加深理解，之后再学习其它的动态规划类型就会容易很多。

• 最优子结构：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
• 重复子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
  线性动态规划是动态规划中变化最多的一类。

首先线性动态规划针对的问题是最常见的数组，字符串，矩阵等，这三种数据结构本身就是线性的，因此出现这些类型的输入的时候，如果要用到动态规划，首先考虑线性动态规划就很合理了，因此很多问题不论最后正解是不是线性动态规划，都会首先想一下线性动态规划是否可行。

其次由于大部分问题的数据都是以这三种形式给出的，因此题目的变化会非常多，很多常见的输入形式以及问题都非常经典，都存在经典的状态设计。因此不考虑一些比较 Trick 的解法，仅仅是经典问题的经典状态设计，就比其它种类的动态规划问题多很多了。

例如单个数组或字符串上设计一维状态，两个数组或字符串上设计两维状态，以及矩阵上设计两维状态等等，同时以上三种情况的状态设计都有可能再加上额外的指标的状态，就是前面例题中的 state，这里面变化就很多了，比如有的题目在 state 这一维上要使用二分，贪心的策略，有的题目需要 DP 状态与数据结构配合来解决问题。

除此之外还有一类问题没有显式的数组，字符串，但是在求解的时候依然满足前面提到的动态规划三条基本概念，可以用动态规划求解，这种问题通常也是线性动态规划。

如此多的变化仅仅这几篇中列举的题目是远远不够的，因此还要多见多练多记。

下一篇开始讨论动态规划另一大类问题：前缀和。