当前位置: 首页> 财经> 产业 > 动态规划算法:09.路径问题_最小路径和_C++

动态规划算法:09.路径问题_最小路径和_C++

时间:2025/8/27 0:48:25来源:https://blog.csdn.net/2302_76267737/article/details/142326587 浏览次数:0次

目录

题目链接:LCR 099. 最小路径和 - 力扣(LeetCode)

一、题目解析

题目:

解析:

二、算法原理

1、状态表示

2、状态转移方程

3、初始化

dp表初始化:

特殊位置初始化:

4、填表顺序

5、返回值

三、编写代码


题目链接:LCR 099. 最小路径和 - 力扣(LeetCode)

一、题目解析

题目:

解析:

  从左上角出发,到达右下角,每次只能向右或者向下走,求一条路径,使得走过的路径和最小

  拿示例一为例:

从左上角到右下角有很多路径可以走,但是只有图中走法路径和才会最小,这种题做过无数遍了吧

二、算法原理

1、状态表示

我们在状态标识的时候,一般都会创建一个数组dp,也就是我们所说的dp表,我们要做的就是把每一个状态的值填入这个表内,最终这个表内的某一个值可能就是我们要返回的值。 

  状态简单理解就是dp表内某一个值代表的含义。

如何确定状态表示

  • 题目要求

   简单的题目里一般会给出

  • 经验+题目要求

  越学越深入,动态规划也是熟能生巧,在题目中没有明显给出的时候,我们就要凭借自己做题的经验来确定,所以就需要我们大量的做题。

  • 分析问题的过程中,发现重复子问题

 分析问题的过程中把重复子问题抽象成我们的状态表示,这个更难理解,一切的基础都是我们先对动态规划算法熟练运用。我也不懂,我们慢慢来。

综上:我们通常会以一个位置为结尾或者开始求得我们想要的答案

那我们的这道题得状态表示是什么样的:

根据经验,我们以一个位置为结尾作答

状态表示:dp[i][j]表示:到达该位置时,路径和达到最小

2、状态转移方程

 确定状态表示之后我们就可以根据状态标识推出状态转移方程

  状态转移方程是什么?

不讲什么复杂的,简单来说状态转移方程就是    dp[i][j]等于什么 dp[i][j]=?

  这个就是状态转移方程,我们要做的,就是推出dp[i][j]等于什么

  我们根据状态表示再结合题目+经验去推理转移方程,这一步也是我们整个解题过程中最难的一步

  我们在这道题先简单了解下什么是状态转移方程,之后比较难的题目再细推

  状态转移方程推理: 

    我们想要知道dp[i][j],也就是(i,j)位置的最小路径和,我们要清楚我们是怎么到达(i,j)位置的

我们从题目中已知,我们可以向下或者向右走,所以我们静观(i,j)位置,我们可以知道,可以从    (i-1,j)位置向下,或者(i,j-1)位置向右都可以到(i,j)位置

示例图:

  我们知道dp表示的是到达一个位置的最小路径和,我们想知道dp[i][j],那就需要知道到达(i,j)位置前位置的最小路径和,也就是dp[ i-1 ][ j ]或者dp[ i ][ j-1 ],至于是哪一个,我们需要比较他们两个的大小,选择最小的一个,最终再加上(i,j)位置的路径数,就是dp[ i ][ j ]了

状态转移方程:dp[i][j]=min( dp[ i-1 ][ j ] , dp[ i ][ j-1 ] )  + (i,j)位置的路径数

3、初始化

 我们创建dp表就是为了把他填满,我们初始化是为了防止在填表的过程中越界

怎么谈越界?

我们在填dp[0][0]时,我们会发现,到达该位置前的两个位置根本不存在

dp表初始化:

所以我们在初始化的时,需要额外增加一行一列,放置越界

特殊位置初始化:

  我们新增的一行一列,我们需要对其数据进行初始化,避免在与原有数据在比较大小时使填表受到影响,我们所求的是最小路径,所以在比较时,会选择最小的值来填表,那我们就在初始化时,把整个dp表的值初始化为INT_MAX,这样就不会影响原有数据的填表

  dp[0][0]位置最为特殊,没有与原有数据作比较,比较的是新增的两个位置的数据大小,如果都为INT_MAX的话,因为都是相同的INT_MAX,min函数比较时会把INT_MAX认为最小值,那会使刚开始填表就错误,之后的填表也不会正确,所以我们应该把这两个位置的值设置为0

4、填表顺序

从上到下,从左到右,依次填表

5、返回值

dp表的最后一个值

三、编写代码

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();
//1、创建dp表,并把所有元素初始化为INT_MAXvector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
//2、特殊位置初始化dp[0][1]=0;dp[1][0]=0;
//3、填表for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];}}
//4、返回值return dp[m][n];}
};

关键字:动态规划算法:09.路径问题_最小路径和_C++

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: