leetcode_【62】不同的路径

1.题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

2.解题思路

动态规划

（1）初始化

1) 从[0,0]走到[0,0]的路径，即没走，设dp[0][0] = 0;

2) 如果m*n的n为1，即机器人在m*1走，只能有一条路径，即arr[i][0] = 1;

3) 如果m*n的m为1，即机器人在1*n走，只能有一条路径，即arr[0][1] = 1;

(2) 动态规划核心算法

机器人每次只能向下或者向右移动一步。即机器人arr[i][j]的路径由arr[i-1][j]和arr[i][j-1]决定，即arr[i][j] = arr[i-1][j]+arr[i][j-1];

3.代码

class Solution {
 public static int uniquePaths(int m, int n) {
        if(m < 0 || n < 0)
            return 0;
        int arr[][] = new int[m][n];
        //初始化
        arr[0][0] = 0;
        //初始化列
        for(int i = 0;i<n;i++){
            arr[0][i] = 1;
        }
        //初始化行
        for(int i = 0;i<m;i++){
            arr[i][0] = 1;
        }
        //动态规划
        for(int i =1;i<m;i++){
            for(int j = 1;j<n;j++){
                arr[i][j] = arr[i-1][j]+arr[i][j-1];
            }
        }
        return arr[m-1][n-1];
    }
}

4.提交记录