62. 不同路径

发布时间:2023年12月18日

不同路径

描述 :

一个机器人位于一个?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];
    }
} 

这期就到这里 , 下期见!

文章来源:https://blog.csdn.net/sytdsqzr/article/details/135029472
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。