首页 > 试题广场 >

不同路径的数目(一)

[编程题]不同路径的数目(一)

热度指数：109288 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

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

数据范围： $0 < n,m \le 100$ ，保证计算结果在32位整型范围内

要求：空间复杂度 $O(nm)$ ，时间复杂度 $O(nm)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(min(n,m))$

示例1

输入

2,1

输出

示例2

输入

2,2

输出

算法知识视频讲解

查看答案及解析

Java

牛客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号

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

排列组合罢了。

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

有比我更简单的吗? 想要优化重复计算，在代码中加入一个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

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

	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

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

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

动态规划

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)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int uniquePaths (int m, int n) {
        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-07-22 17:57:20 回复(0)

Java

牛客839384289号

    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-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }

发表于 2022-06-16 23:00:15 回复(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
        //二维数组
        
        //记录方案
        int[][] dp = new int[m][n];
        //m = row
        dp[0][0] = 1;
        //n = col
        for(int i = 1;i<n;i++){
            dp[0][i] = 1;
        }
        for(int i = 1;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-05-10 10:46:20 回复(0)

Java

精灵鼠201906031611131

看看有优化的余地吗。怎么减去初始化第一行和第一列

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    
    int count  = 0;
    public int uniquePaths (int m, int n) {
        // write code here
        
        //使用递归
        /*
        
         if(m <= 0 || n <= 0)
            return 0;
        
        //follow数学题解
        if(m == 1)
            return 1;
        
        if(n == 1)
            return 1;
        
        return uniquePaths(m-1,n) + uniquePaths(m, n-1);
        
        */
        
        if(m==1)
            return 1;
        if(n==1)
            return 1;
       
        int[][] array = new int[m][n];
     
        for(int i = 0; i<n; i++) {
            array[0][i] = 1;
        }
        
        for(int i = 0; i<m ; i++) {
            array[i][0] = 1;
        }
        
        for(int i = 1; i<m; i++) {
            for(int j = 1; j<n; j++) {
                array[i][j] = array[i-1][j] + array[i][j-1];
            }
        }
        
        return array[m-1][n-1];
    }

}

发表于 2022-04-21 12:01:35 回复(0)