动态规划前路径问题
路径问题：本章讲三角形最小路径和（Leetcode 120中等）、下降路径最小和(Leecode 931 中等）、下降路径最小和 II（Leedcode 1289 困难）
文章目录
前言
路径问题作为经典动态规划问题背包问题的前传，用于理解dp动态规划的思想模型。本文着重讲解当问题复杂之后，如何去找转移方程、优化空间、时间复杂度
提示：以下是本篇文章正文内容，下面案例可供参考
一、三角形最小路径和（Leetcode 120中等）
1.问题描述
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
2.问题分析
此问题由之前的计算路径的矩形转换成了三角形，那么可以通过遍历时只遍历上三角或者下三角。
2.1 定义数据结构
问题是有多少不同的路径，此时应当使用dp[m-1][n-1]来表达最终的结果，这个和前文没啥区别
2.2 结构含义的解读
本问题中dp[i][j]就可以解读为：i代表地图的行，j代表列
2.3 状态转移方程的建立
本问题中：
如下图，地图为一个三角形且规定了相邻的结点，因此我们只能往下或者往右下角移动，因此我们按照「当前可选方向」进行分析：
当前位置只能 「往下」 移动，即有 dp[i][j] = dp[i-1][j]+grid[i][j]
当前位置只能 「往右下」 移动，即有 dp[i][j] = dp[i-1][j-1]+grid[i][j]
当前位置即能 「往下」 也能 「往右下」 移动，即有dp[i][j] =min（dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]）
推导过程：
dp[i][j]代表的是到达地图grid[i][j]点到达路径的经过的路径和，那么往上递推一步：如何到达grid[i][j]点，只有两种方法：由前面的点往下或者往右下进入到这个点,因此到达grid[i][j]的和就只有到达dp[i][j-1]的和+ triangle[i][j]、dp[i-1][j-1]+triangle[i][j]两种可能，并取其中更小的,由此可推导出dp[i][j]的状态转移方程：dp[i][j] =min（dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]）
3.代码展示：
代码如下（示例）：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
int n=triangle[m-1].size();
vector<vector<int>> dp(m, vector<int>(n));
dp[0][0]=triangle[0][0];
for(int i=0;i<m;i++)
{
for(int j=0;j<=i;j++)
{
if(i-1>j||i-1==j)
{
if(i>0&&j>0)
{
dp[i][j]=min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]);
}
else if(i>0)
{
dp[i][j]=dp[i-1][j]+triangle[i][j];
}
}
else
{
if(i>0&&j>0)
{
dp[i][j]=dp[i-1][j-1]+triangle[i][j];
}
}
}
}
int minSum=dp[m-1][0];
for(int i=1;i<n;i++)
{
if(dp[m-1][i]<minSum)
{
minSum=dp[m-1][i];
}
}
return minSum;
}
};
4.升级：优化算法
我们在递推的过程中发现，其实第i+1行的值只会依赖于第i行的结果，因此在空间上可以只申请2*n。如下图所示：比如第一行的计算出来的结果放在二维数组的第一行，第二行根据第一行的结果放在第二行，当计算第三行结果的时候，此时第一行的结果已经无效了，因此可以使用第三行的结果覆盖掉第一行的数据。
5.优化算法的代码展示
代码如下（示例）：
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int m=triangle.size();
int n=triangle[m-1].size();
vector<vector<int>> dp(2, vector<int>(n));
dp[0][0]=triangle[0][0];
for(int i=0;i<m;i++)
{
for(int j=0;j<=i;j++)
{
if(i-1>j||i-1==j)
{
if(i>0&&j>0)
{
dp[i&1][j]=min(dp[(i-1)&1][j]+triangle[i][j],dp[(i-1)&1][j-1]+triangle[i][j]);
}
else if(i>0)
{
dp[i&1][j]=dp[(i-1)&1][j]+triangle[i][j];
}
}
else
{
if(i>0&&j>0)
{
dp[i&1][j]=dp[(i-1)&1][j-1]+triangle[i][j];
}
}
}
}
int minSum=dp[(m-1)&1][0];
for(int i=1;i<n;i++)
{
if(dp[(m-1)&1][i]<minSum)
{
minSum=dp[(m-1)&1][i];
}
}
return minSum;
}
};
二、下降路径最小和(Leecode 931 中等）
1.问题描述
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
2.问题分析
此问题由上个问题的计算路径的三角形转换成了矩形，这次直接使用升级后的算法分析
2.1 定义数据结构
问题是有多少不同的路径，此时应当使用dp[m-1][n-1]来表达最终的结果，这个和前文没啥区别
2.2 结构含义的解读
本问题中dp[i][j]就可以解读为：i代表地图的行，j代表列
2.3 状态转移方程的建立
如下图，地图规定了相邻的结点，因此我们只能往下或者往右下角或者左下角移动，因此我们按照「当前可选方向」进行分析：
当前位置只能 「往下」 移动，即有 dp[i][j] = dp[i-1][j]+matrix[i][j]
当前位置只能 「往左下」 移动，即有 dp[i][j] = dp[i-1][j+1]+matrix[i][j]
当前位置只能 「往右下」 移动，即有 dp[i][j] = dp[i-1][j-1]+matrix[i][j]
当前位置即能 「往下」 也能 「往右下」 移动，即有 dp[i&1][j]=min(dp[(i-1)&1][j-1],min(dp[(i-1)&1][j],dp[(i-1)&1][j+1]))+matrix[i][j];
2.4.代码展示：
代码如下（示例）：
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n=matrix.size();
vector<vector<int>>dp(2,vector<int>(n,0));
dp[0][0]=matrix[0][0];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==0)
{
dp[i][j]=matrix[i][j];
}
else
{
if(j!=0&&j!=n-1)
{
dp[i&1][j]=min(dp[(i-1)&1][j-1],min(dp[(i-1)&1][j],dp[(i-1)&1][j+1]))+matrix[i][j];
}
if(j==0)
{
dp[i&1][j]=min(dp[(i-1)&1][j],dp[(i-1)&1][j+1])+matrix[i][j];
}
if(j==n-1)
{
dp[i&1][j]=min(dp[(i-1)&1][j-1],dp[(i-1)&1][j])+matrix[i][j];
}
}
}
}
int res = dp[(n-1)&1][0];
for (int i = 0; i < n; i++) res = min(res, dp[(n - 1)&1][i]);
return res;
}
};
二、下降路径最小和 II(Leecode 1289 困难）
1.问题描述
给你一个 n x n 整数矩阵 arr ，请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
2.问题分析
此问题和之前不同的是，第i+1行可以从第i行的任一位置过来，除了同一列的。首先按照原有思路求解，随后再说如何优化：
2.1 定义数据结构
问题是所有路径和，此时应当使用dp[m-1][n-1]来表达最终的结果，这个和前文没啥区别
2.2 结构含义的解读
本问题中dp[i][j]就可以解读为：i代表地图的行，j代表列
2.3 状态转移方程的建立
此处已经没有固定的方向了，因此需要通过遍历上一行除了同一列的所有值：dp[i][j]=min(dp[i-1][0],dp[i-1][1]…dp[i-1][n])+arr[i][j];
3.代码展示：
代码如下（示例）：
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int n=grid.size();
vector<vector<int>>dp(2,vector<int>(n,0));
dp[0][0]=grid[0][0];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==0)
{
dp[i][j]=grid[i][j];
}
else
{
int br=INT_MAX;
for(int m=0;m<n;m++)
{
if(m!=j){
br=min(br,dp[(i-1)&1][m]);
}
}
dp[i&1][j]=br+grid[i][j];
}
}
}
int res = dp[(n-1)&1][0];
for (int i = 0; i < n; i++) res = min(res, dp[(n - 1)&1][i]);
return res;
}
};
4.升级：优化算法
我们在递推的过程中发现，其实第i+1行的值只会依赖于第i行的最小值和次最小值，当最小值所在的列和当前列在同一列，只能选择次最小值，否则选择最小值。因此在计算过程中，只需要定义两个临时变量保存上一行的最小值和次最小值即可。第一行的这两个值单独处理。
5.代码展示：
代码如下（示例）：
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int n=grid.size();
int dp[n][n];
dp[0][0]=grid[0][0];
int _min=-1;
int _Maxmin=-1;
for (int i = 0; i < n; i++) {
int val = grid[0][i];
dp[0][i] = val;
if (val < (_min == -1 ? INT_MAX : dp[0][_min])) {
_Maxmin = _min;
_min = i;
} else if (val < (_Maxmin == -1 ? INT_MAX : dp[0][_Maxmin])) {
_Maxmin = i;
}
}
for(int i=1;i<n;i++)
{
int min=-1;
int Maxmin=-1;
for(int j=0;j<n;j++)
{
dp[i][j] = INT_MAX;
if(j!=_min)
{
dp[i][j]=dp[i-1][_min]+grid[i][j];
}
else{
dp[i][j]=dp[i-1][_Maxmin]+grid[i][j];
}
if (dp[i][j] < (min == -1 ? INT_MAX : dp[i][min])) {
Maxmin = min;
min = j;
} else if (dp[i][j] < (Maxmin == -1 ? INT_MAX : dp[i][Maxmin])) {
Maxmin = j;
}
}
_min=min;
_Maxmin=Maxmin;
}
int res = dp[(n-1)][0];
for (int k = 0; k < n; k++) res = min(res, dp[(n - 1)][k]);
return res;
}
};
总结
本文主要着重讲述了在状态转移方程方面的优化方式，主要是分析是否第i+1行和前面的所有行都有关系还是只和上一行有关。leecode 931我们可以分析出当前行只和上一行存在联系，因此可以优化空间复杂度nxn–>2*n,leecode 1289我们可以发现当前行只和上一行的最小值和此最小值有关，因此时间复杂度由n的三次方优化为n的平方。下文的统计所有可行路径（困难）【记忆化搜索】，由于很难直接从动态规划求解，因此先去学习DFS，在从dfs转换成动态规划。下一章开始DFS的学习，学有所成再来解此题。
