【算法学习笔记】不同路径——动态规划类题目的做题思路

前置知识【算法学习笔记】动态规划入门——从最简单的问题开始动态规划-CSDN博客一、题目一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1输入m 3, n 7输出28二、思路1.对于动态规划这种通过一些小问题来求解最终大问题的题目。我们首先要确定的就是我们要求的小问题是什么也就是先要确定每个状态代表什么dp数组存储的是什么。对于本题我们的大问题是从起点到终点的路径数量。不难发现要求到终点的路径数量就要知道终点左和上两个的路径数量以此往起点类推我们就要求到达每个格的路径数量。所以我们要记录的状态就是到达某个格的所有路径数量。由于这是一个二维表格所以我们建立一个二维dp数组去储存到达每个位置的路径即可。2.确定完之后我们就要想第一个前几个状态是什么因为后面的状态我们可以通过前面的状态去递推但是第一个前几个状态我们是没法推出来的。在这里我们初始化到达起点的总路径数为1。为什么不是0在确定状态含义的时候我们已经确定状态的含义为“到达某个格的所有路径数量”。到达某个地方有0条路径的意思是我们到不了这个地方而我们显然是能到起点的所以应初始化为1。3.接下来我们要确定状态转移方程。我们现在初始化了第一个状态但是我们还不知道该如何通过前面的状态去推导后面的状态。对于本题某个格子只能从他的上面或者左边到达所以不难看出dp[x][y] dp[x - 1][y] dp[x][y - 1]。当这个格子贴着上或者左边界时其只能通过左或者上格子到达直接等于左或者上格子的路径数即可。需要注意动态规划中经常可能遇见这种在边界或者有特殊情况需要分类讨论不要遗忘。4.对于更加复杂一些的动态规划题目遍历顺序可能不再是简单的从前往后但是对于本题来说从起点向终点遍历即可。三、代码int uniquePaths(int m, int n) { vectorvectorint dp(m, vectorint(n));//到达mn的路径数量 dp[0][0] 1; for(int i 0; i m; i) { for(int j 0; j n; j) { if(i 0 j 0) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } else if(i 0) { dp[i][j] dp[i - 1][j]; } else if(j 0) { dp[i][j] dp[i][j - 1]; } } } return dp[m - 1][n - 1]; }