62. 不同路径

不同路径

描述 :

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

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

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

题目 :

LeetCode 62.不同路径 :

62. 不同路径

解析 :

第一种方式 : (递归 , 但是这种会超时间限制)

class Solution {
    public int uniquePaths(int m, int n) {
        return dp(m,n);
    }
     public int dp(int m,int n){
         if(n == 1 || m == 1){
             return 1;
         }
         return dp(m - 1,n) + dp(m,n - 1);
     }
} 

第二种方式 : (二维数组)

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] arr = new int[m][n];
        arr[0][0] = 1;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(i > 0 && j > 0){
                    arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
                }else if(i > 0){
                    arr[i][j] = arr[i - 1][j];
                }else if(j > 0){
                    arr[i][j] = arr[i][j - 1];
                }
            }
        }
        return arr[m - 1][n - 1];
    }
} 

这期就到这里 , 下期见!