首页 > 试题广场 >

不同路径的数目(一)

[编程题]不同路径的数目(一)
  • 热度指数：121576 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一个机器人在m×n大小的地图的左上角（起点）。
机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围：，保证计算结果在32位整型范围内
要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

2,1

输出

1
示例2

输入

2,2

输出

2
算法知识视频讲解
添加回答
Java
西北卓越青年头像 西北卓越青年
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        return (m==1||n==1)?1:uniquePaths(m-1,n)+uniquePaths(m,n-1);
        // write code here
    }
}
发表于 2025-04-16 13:55:14 回复(0)
Java
fukkk头像 fukkk 
public int uniquePaths (int m, int n) {
        int dp[][] = new int[m+1][n+1];
        dp[0][1]=1;
        for(int i=1; i<m+1;i++){
            for(int j=1; j<n+1;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }

优雅写法  无需初始化
发表于 2025-03-10 17:38:44 回复(0)
Java
牛客812212514号头像 牛客812212514号
用递归，哦豁，超时    

public int uniquePaths (int m, int n) {
        // write code here
        return paths(1,1,m,n);
    }

    public int paths(int i,int j,int m,int n){
 
        if(i>=m&&j>=n){
            return 1;
        }
        if(i>=m&&j<n){
            return paths(i+1,j+1,m,n);
        }
         if(i<m&&j>=n){
            return paths(i+1,j+1,m,n);
        }
        return paths(i+1,j,m,n)+paths(i,j+1,m,n);

    }
}
发表于 2024-10-21 15:46:56 回复(0)
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
        // 算法核心思想：记忆化搜索

        // dp[i][j]表示当位置落在i,j上时，有几种走法可以到达m-1,n-1
        // 初始化-1
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }

        return process(m, n, 0, 0, dp);
    }

    public int process (int m, int n, int i, int j, int[][] dp) {
        // 递归出口
        if (i == m - 1 && j == n - 1) {
            dp[i][j] = 1;
            return dp[i][j];
        }

        // 递归分支
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        // 往下走
        int d = 0;
        if (i < m - 1) {
            // 不会越界，可以走
            if (dp[i + 1][j] == -1) {
                dp[i + 1][j] = process(m, n, i + 1, j, dp);
            }
            d = dp[i + 1][j];
        }
        // 往右走
        int r = 0;
        if (j < n - 1) {
            // 不会越界，可以走
            if (dp[i][j + 1] == -1) {
                dp[i][j + 1] = process(m, n, i, j + 1, dp);
            }
            r = dp[i][j + 1];
        }

        // 本位置的走法，等于向右走的走法 + 向下走的走法
        dp[i][j] = d + r;
        return dp[i][j];
    }
}

发表于 2024-09-23 21:29:09 回复(0)
Java
形而上学的锋头像 形而上学的锋
2行代码搞定 
 public int uniquePaths (int m, int n) {
        if(m==1 || n==1) return 1;
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }


发表于 2023-09-12 20:18:13 回复(0)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
public int uniquePaths (int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    dp[i][j]=1;
                }else if(i==0){
                    dp[i][j]=1;
                }else if(j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
        }
        return dp[m-1][n-1];
    }

发表于 2023-07-11 16:51:53 回复(0)
Java
时长两年半焦虑人头像 时长两年半焦虑人
public class Solution {
    public int uniquePaths (int m, int n) {
        if(m==1||n==1) return 1;
        else return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
}
发表于 2023-06-25 23:54:31 回复(0)
Java
牛客486811008号头像 牛客486811008号
public class Solution {
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        if(m == 1)return 1;
        if(n == 1)return 1;
        return uniquePaths(m, n-1) + uniquePaths(m-1, n);
    }
}
发表于 2023-05-21 16:23:30 回复(0)
Java
offerslayer头像 offerslayer
排列组合罢了。 
import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here

    return Combination(m+n-2, m-1);
    }


	private static int Combination(int n, int k) {
		if(k==0||k==n)
			return 1;
		else
			return Combination(n-1, k)+Combination(n-1, k-1);
	}
}


发表于 2023-05-06 14:06:58 回复(0)
Java
万兵0610头像 万兵0610
有比我更简单的吗? 想要优化重复计算，在代码中加入一个hashMap保存即可 
import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here

        if(m == 1){
            return 1;
        }else if(n == 1 ){
            return 1;
        }

        return uniquePaths(m-1, n) + uniquePaths(m, n-1);

    }

}


发表于 2022-12-12 09:51:52 回复(0)
Java
T丶KOATH头像 T丶KOATH
public int uniquePaths (int m, int n) {
        // write code here
        if(m==1&&n==1) return 1;
        else if(m==1&&n>1) return uniquePaths(m,n-1);
        else if(n==1&&m>1) return uniquePaths(m-1,n);
        else return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }


居然超时了
发表于 2022-10-23 21:55:36 回复(0)
Java
BlueProtocol头像 BlueProtocol 
	public int uniquePaths (int m, int n) {
		// write code here
		int dp[][] = new int[m][n];
		for (int i = 0; i < n; i++) {
			dp[0][i] = 1;
		}
		for (int i = 0; i < m; i++) {
			dp[i][0] = 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];
			}
		}
		return dp[m-1][n-1];
	}

发表于 2022-10-13 09:26:06 回复(0)
Java
INEEDSSD头像 INEEDSSD 
import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 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];
            }
        }
        
        return dp[m - 1][n - 1];
    }
}

发表于 2022-09-16 09:32:30 回复(0)
Java
超可爱超超头像 超可爱超超 
 public static int uniquePaths(int m, int n) {

        //当m=1.或者n=1时只有一种
        //否则都是两种
        if (m==1||n==1){
            return 1;
        }

        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }

发表于 2022-09-05 16:59:39 回复(1)
Java
一码归一码头像 一码归一码 
public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }else{
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

发表于 2022-08-25 17:11:26 回复(0)
Java
牛客用户007头像 牛客用户007 
import java.util.*;


public class Solution {
    /**
     *
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here

        if (m == 1 || n == 1) return 1;

        int[][] dp = new int[m][n];

        for (int i = 1; i < m; i ++) dp[i][0] = 1;
        for (int i = 1; i < n; i ++) dp[0][i] = 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];
            }
        }

        return dp[m - 1][n - 1];
    }
}

发表于 2022-08-13 10:15:13 回复(0)
Java
FARO_Z头像 FARO_Z

动态规划

public int uniquePaths (int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j <n+1 ; j++) {
                if (i==1 || j==1) {
                    dp[i][j]=1;
                } else {
                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
发表于 2022-07-23 21:33:03 回复(0)
提交观点

问题信息

动态规划
难度：
69条回答 33105浏览

热门推荐

通过挑战的用户

查看代码

相关试题

不同路径的数目(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号