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

前置知识

【算法学习笔记】动态规划入门——从最简单的问题开始动态规划-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) { vector<vector<int> > dp(m, vector<int>(n));//到达（m，n）的路径数量 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]; }