当前位置：网站首页>动态规划前路径问题优化方式
动态规划前路径问题优化方式
2022-07-06 09:25:00 【爱学习的小耿】
动态规划前路径问题
路径问题：本章讲三角形最小路径和（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的学习，学有所成再来解此题。
边栏推荐
- 遇到程序员不修改bug时怎么办？我教你
- Research Report on market supply and demand and strategy of China's medical chair industry
- Mysql database (III) advanced data query statement
- STM32 learning record: input capture application
- STM32学习记录：输入捕获应用
- LeetCode＃204. Count prime
- JS --- detailed explanation of JS DOM (IV)
- What are the commonly used SQL statements in software testing?
- Threads and thread pools
- STM32 learning record: play with keys to control buzzer and led
猜你喜欢
Threads et pools de threads
Stm32 dossiers d'apprentissage: saisie des applications
Pedestrian re identification (Reid) - Overview
Jupyter installation and use tutorial
How to become a good software tester? A secret that most people don't know
Crawler series of learning while tapping (3): URL de duplication strategy and Implementation
ucore lab7
What are the software testing methods? Show you something different
The wechat red envelope cover designed by the object is free! 16888
LeetCode＃62. Different paths
随机推荐
Learning record: understand systick system timer and write delay function
JDBC introduction
STM32學習記錄：輸入捕獲應用
Research Report on pharmaceutical R & D outsourcing service industry - market status analysis and development prospect forecast
[pytorch] simple use of interpolate
线程及线程池
Es6---es6 content details
ucore lab 2
学习记录：串口通信和遇到的错误解决方法
MySQL数据库（二）DML数据操作语句和基本的DQL语句
学习记录：理解 SysTick系统定时器，编写延时函数
学习记录：USART—串口通讯
Jupyter installation and use tutorial
LeetCode＃2062. Count vowel substrings in strings
MATLAB实例：阶跃函数的两种表达方式
ArrayList set
LeetCode＃268. Missing numbers
Research Report on medical anesthesia machine industry - market status analysis and development prospect prediction
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
How to do agile testing in automated testing?