动态规划五部曲——力扣周总结_动规五部曲

本文是根据代码随想录内容所改编，里面加了自己一些笔记，主要内容版权归代码随想录所有，详情请见代码随想录网站，该文是为了自己回忆和方便温习。

62、不同路径力扣链接

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

输入：m = 3, n = 7 输出：28

总结动态规划算法五部曲：

1、确定dp数组和下标含义：
2、确定递推公式
3、dp数组的初始化
4、确定遍历顺序
5、举例推导dp数组

就本题分析:
机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
1、dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径;

2、递推公式：(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];

3、初始化：起点 (0,0) 到 (i,0) 和 (0,j) 都只有一条路径。即起点到首列和首行都初始化为1，dp[i][0],dp[0][j] 都为1;

4、遍历顺序 ：由递推公式可知，(i,j)的状态需要靠(i-1,j)和(i,j-1)的状态，所以dp[i][j]是从其上方和左方推导而来，从左到右一层一层遍历就可以了。

5、举例推导dp数组：

java代码如下：

public static int uniquePaths(int m, int n){
   
    int[][] dp = new int[m][n];//1、定义dp数组
    for(int i = 0; i < m; i++){
   
       dp[i][0] = 1;//首列初始化为1
    }
    for(int j = 0; j < n; j++){
   
       dp[0][j] = 1;//首行初始化为1
    }
    for(int i = 1; i < m; i++){
   
       for(int j = 1; j < n; j++){
   //遍历顺序
          dp[i][j] = dp[<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15