秒懂【不同路径】！动态规划一步步拆解。

1.思路

本题给定了一个矩阵，从左上角到右下角移动，移动的方向为：向右或者向下。因此：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (从上面下来 或者从左边过来)。

alt

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param m int整型
# @param n int整型
# @return int整型
#
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # write code here
        # 1.定义状态.	i：地图的行; j：地图的列; dp[i][j]:从(0,0)到达地图坐标为(i,j)时的路径数
        dp = [[0] * n for _ in range(m)]
        # 2.初始化边界条件：dp[i][0]=1；只有一列，因此只有一种走法（向下走）;dp[0][j]=1：只有一行，因此只有一种走法（向右走）
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        # 3. 确定递推公式： dp[i][j] = dp[i - 1][j] + dp[i][j - 1]:从上面下来 或者 从左边过来
        for i in range(1, m):
            for j in range(1, n):
                # 路径数等于左方格子的路径数加上上方格子的路径数
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]  # (从上面下来 或者从左边过来)
        # 4.  输出结果
        return dp[m - 1][n - 1]

2.2 Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        //1.定义状态.  i：地图的行; j：地图的列; dp[i][j]:从(0,0)到达地图坐标为(i,j)时的路径数
        int[][] dp = new int[m][n];
        //2.初始化边界条件：dp[i][0]=1；只有一列，因此只有一种走法（向下走）;dp[0][j]=1：只有一行，因此只有一种走法（向右走）
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        //3.确定递推公式： dp[i][j]= dp[i-1][j] + dp[i][j-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];//(从上面下来 或者从左边过来)
            }
        }
        //4.输出结果
        return dp[m - 1][n - 1];
    }
}

2.3 Go代码

package main



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param m int整型
 * @param n int整型
 * @return int整型
 */
func uniquePaths(m int, n int) int {
	// write code here
	//1.定义状态.	i：地图的行; j：地图的列; dp[i][j]:从(0,0)到达地图坐标为(i,j)时的路径数
	dp := newArray(m, n)
	//2.初始化边界条件：dp[i][0]=1；只有一列，因此只有一种走法（向下走）;dp[0][j]=1：只有一行，因此只有一种走法（向右走）
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	//3.确定递推公式： dp[i][j]= dp[i-1][j] + dp[i][j-1] :从上面下来 或者从左边过来
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			//路径数等于左方格子的路径数加上上方格子的路径数
			dp[i][j] = dp[i-1][j] + dp[i][j-1] //(从上面下来 或者从左边过来)
		}
	}
	//4.输出结果：
	return dp[m-1][n-1]
}

// 创建一个 m行n列的矩阵（二维数组）
func newArray(m int, n int) [][]int {
	arr := make([][]int, m)
	for i := 0; i < m; i++ {
		arr[i] = make([]int, n)
	}
	return arr
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构