网站项目建设人员规划,wordpress 支付宝赞助,线上编程课推荐哪一个,济南网站建设(力推聚搜网络)1. 题目解析
题目链接#xff1a;62. 不同路径 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了。
2.算法原理
想要解决这个问题#xff0c;我们得像个侦探一样#xff0c;一步步地追踪路径#xff0c;找出所有可能的走法。接下…1. 题目解析
题目链接62. 不同路径 这个问题的理解其实相当简单只需看一下示例基本就能明白其含义了。
2.算法原理
想要解决这个问题我们得像个侦探一样一步步地追踪路径找出所有可能的走法。接下来让我们一步步地拆解这个问题看看怎么找到答案。
动态规划问题还是经典五步走~
一、设定状态表
想象你站在一个棋盘上你的任务是找出从起点到终点有多少种不同的走法。在这个问题里我们可以设定一个状态表来记录每一步的可能性。
具体来说我们用dp[i][j]来表示到达棋盘上的第i行第j列位置时有多少种走法。这样我们只需要关注当前位置而不需要考虑之前是怎么走过来的。
二、分析状态转移
现在假设你站在[i, j]这个位置想要知道到达这里有多少种走法。显然你可能是从上方[i-1, j]位置走下来的也可能是从左方[i, j-1]位置走过来的。
因此我们可以得出一个结论到达[i, j]位置的走法数就是到达上方位置[i-1, j]的走法数与到达左方位置[i, j-1]的走法数之和。用数学公式表示就是dp[i][j] dp[i-1][j] dp[i][j-1]。
三、初始化状态表
在填表之前我们需要给状态表一个初始值。通常我们可以在棋盘的最前面加一列和一行作为辅助结点来帮助我们进行初始化。
在这个问题里我们只需要在棋盘的最上方和最左边各添加一个辅助结点并将左上角的辅助结点dp[0][1]初始化为1因为从起点开始只有一种走法。这样我们就可以开始填表了。
四、按顺序填表
填表的顺序很关键。由于我们是根据上方和左方的状态来推算当前位置的状态所以我们需要按照从上到下、从左到右的顺序来填表。这样当我们填写某个位置时它上方和左方的位置都已经填好了我们就可以直接引用它们的结果。
五、找出答案
最后当我们填完整个状态表后答案就藏在最后一个位置dp[m][n]里。这个位置记录了从起点到终点的所有可能走法数。
3.代码编写
class Solution
{
public:int uniquePaths(int m, int n) {vectorvectorint dp(m 1, vectorint(n 1));//多开一行一列dp[0][1] 1;//细节在这for(int i 1; i m; i)for(int j 1; j n; j)dp[i][j] dp[i - 1][j] dp[i][j - 1];return dp[m][n];}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
