首页 > 试题广场 >

不同路径的数目(一)

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

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

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

输入

2,1

输出

1
示例2

输入

2,2

输出

2
算法知识视频讲解
添加回答
Java
肥猿头像 肥猿
解题思路：动态规划，状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]; 
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=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];
    }
}


发表于 2021-03-16 10:38:54 回复(0)
Java
放学后我不走~头像 放学后我不走~
除了第一行和第一列，其余的每一格，对于它们来说，每一步都来自上或左，所以走到这些格的可能数为上一步的可能之和，即上方的可能加左方的可能，最后累加到最后一个，就是答案 
public class Solution {
    public int uniquePaths(int m, int n) {
        int a[][] = new int[m][n];
        for(int i=0;i<m;i++)
            a[i][0]=1;
        for(int i=0;i<n;i++)
            a[0][i]=1;
        for(int i=1;i<m;i++)
            for(int j=1;j<n;j++)
                a[i][j] = a[i-1][j]+a[i][j-1];
        return a[m-1][n-1];
    }
}

发表于 2018-08-31 19:21:08 回复(0)
小宝12头像 小宝12
dp[i][j]表示从开始到ij的路径条数   dp[i][j] = dp[i-1][j]+dp[i][j-1]
public class Solution {
    public int uniquePaths(int m, int n) {
        if(m<0 || n<0){
return -1;
}
if(m==0 || n==0){
return 1;
}
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];
    }
}
发表于 2016-03-14 21:36:52 回复(0)
Java
一个天秤座的程序员头像 一个天秤座的程序员
import java.util.*;
public class Solution {
    public int uniquePaths (int m, int n) {
        // write code here
        int dp[][] = new int[m][n];
        Arrays.fill(dp[0],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];
    }
}
发表于 2021-08-23 10:55:21 回复(0)
勇敢牛牛，不怕困难！头像 勇敢牛牛，不怕困难！ 
class Solution {
public:
  /**
   * 
   * @param m int整型 
   * @param n int整型 
   * @return int整型
   */
  int uniquePaths(int m, int n) {
    vector<vector<int>> grid(m, vector<int>(n, 1));
    for (int y = 1; y < m; ++y)
      for (int x = 1; x < n; ++x)
        grid[y][x] = grid[y - 1][x] + grid[y][x - 1];
    
    return grid[m - 1][n - 1];
  }
};

发表于 2021-07-07 07:18:22 回复(0)
Java
失败的cc头像 失败的cc
动态规划 
public class Solution {
    public int uniquePaths(int m, int n) {
        int[] count = new int[n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 || j == 0)
                    count[j] = 1;
                else
                    count[j] = count[j - 1] + count[j];
            }
        }
        return count[n - 1];
    }
}

/*
由题可得出递推方程 
uniquePaths(i, j) = 1; if(i == 0 || j == 0)
uniquePaths(i, j) = uniquePaths(i - 1, j) + uniquePaths(i, j - 1); else 
用一个一维数组存放计算过的值
其中count[j] = uniquePaths(i, j),即从起始点到第i行第j列的路径总数。
*/


发表于 2020-04-11 17:01:32 回复(0)
牛客282965463头像 牛客282965463 
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > dp(m,vector<int>(n,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];
    }
};

发表于 2019-12-24 18:11:10 回复(0)
Java
HW柯可头像 HW柯可 
public class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        //dp[i][j]表示机器人从点（0,0）出发到点（i,j）的不同路径数目
        int dp[][]= new int[m][n];
        dp[0][0] = 0;
        /*考虑边缘情况*/
        //n = 1的情况，只有一条直线路径
        for(int i = 1; i < m; i++){
            dp[i][0] = 1;
        }
        //m = 1的情况，只有一条直线路径
        for(int j = 1; j < n; j++){
            dp[0][j] = 1;
        }
        //动态规划
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                //到达点（i,j）有两种路径：
                //（1）机器人从点（i-1,j）往下移动 （2）机器人从点（i,j-1）往右移动 
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

编辑于 2019-08-14 14:04:43 回复(0)
C/C++
但求八月九月好运！头像 但求八月九月好运！ 
Solution 1
class Solution {
public:
    int hash[102][102]={0};
    int uniquePaths(int m, int n) {
        if(m<=0||n<=0) return -1;
        if(m==1||n==1) return 1;
        if(hash[m][n]!=0) return hash[m][n];
        hash[m][n]=uniquePaths(m,n-1)+uniquePaths(m-1,n);
        return hash[m][n];
    }
};


Solution 2
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> >dp(m,vector<int>(n));
        dp[0][0]=1;
        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];
    }
};

编辑于 2019-06-19 20:48:41 回复(1)
zbbsyx头像 zbbsyx 
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[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];
    }
};

发表于 2019-04-18 10:41:01 回复(0)
NULL6666头像 NULL6666 
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> >dp(m,vector<int>(n,1));//初始化为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];
    }
};

发表于 2018-11-04 22:14:15 回复(0)
我菜得抠脚头像 我菜得抠脚 
public int uniquePaths(int m, int n) {
        if(m<1||n<1) return 0;
        int[][] dp = new int[m+1][n+1];
        //基础状态
        for(int i=1;i<n+1;i++) {
            dp[1][i]=1;
        }
        for(int i=1;i<m+1;i++) {
            dp[i][1]=1;
        }
        //自底向上动态规划
        for(int i=2;i<m+1;i++) {
            for(int j=2;j<n+1;j++) {
                dp[i][j] = dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m][n];
    }

发表于 2018-05-31 22:29:26 回复(0)
疾风剑豪～亚索头像 疾风剑豪～亚索
class Solution {
public:
    //vector<vector<int> > f;
    
    int uniquePaths(int m, int n) 
    {
        //1.动态规划,时间复杂度O(n^2),空间复杂度O(n)
        /*例如下面的3行5列，每个元素代表到达这个地方时有多少种走法
        最终的答案是15
            1  1  1  1   1
            1  2  3  4   5
            1  3  6  10  15
        */
        vector<int> f(n,0);
        f[0] = 1;
        for(int i = 0;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                f[j] = f[j] + f[j-1];
            }
        }
        return f[n-1];
        //2.深搜+缓存----------时间复杂度O(n^2),空间复杂度O(n^2)
        //因为要运行的是这个函数，所以可以把数组声明放在函数外面
        //但是赋值都要在函数内
        //f =vector<vector<int> >(m,vector<int>(n,0));
        //f[0][0] = 1;
        
        //3.深搜-------------时间复杂度为O(n^4),,空间复杂度O(n)
        /*if(m<=0 || n<=0)  深搜，小集合可以过，大集合会超时，这题就超时了。
            return 0;       时间复杂度为O(n^4),因为二叉树树的高度为n，个数为n^4-1.
        if(m==1 && n==1)
            return 1;
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
        */
        
        //下面用深搜+缓存，也就是复杂度下降到O(n^2),因为只算了二叉树的一个子树
        //就把大部分值存储在数组中，然后执行第二个递归函数时，几乎不需要重复计算了
        //return dfs(m-1,n-1);
    }
    /*int dfs(int x,int y)
    {
        if(x==0 && y==0)
            return f[0][0];
        if(x<0 || y<0)
            return 0;
        if(f[x][y]>0)
            return f[x][y];
        else
        {
            return f[x][y] = dfs(x-1,y)+dfs(x,y-1);
        }
    }*/
    
};
发表于 2018-05-06 13:41:11 回复(0)
不服输的大灰狼头像 不服输的大灰狼
//动态规划加二维数组。
//从左上角逐步向左、向下求解 
int uniquePaths(int m, int n) 
{
    //map<string, int> pathNum;
    vector<int> line(n, 0);
    vector<vector<int>> pathNum(m, line);
    for (int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            // (i,j) = (i-1) + (m-1)
            
            if (i == 0 || j == 0)
            {
                pathNum[i][j] = 1;
                continue;
            }
            int temp = pathNum[i - 1][j] + pathNum[i][j - 1];
            pathNum[i][j] = temp;
        }
    }
    return pathNum[m - 1][n - 1];
}

发表于 2018-03-27 14:40:40 回复(0)
Flynn_Thiago头像 Flynn_Thiago
动态规划   
 int dpuniquePaths(int** arr, int x, int y)
    {
        if(arr[x][y]>0)
            return arr[x][y];
        return arr[x][y] = dpuniquePaths(arr,x-1,y)+dpuniquePaths(arr,x,y-1);
    }

    int uniquePaths(int m, int n) {
        int **uniq_path = new int*[m];
        for(int x =0;x<m;x++)
        {
            uniq_path[x] = new int[n];
            memset(uniq_path[x],0,n*sizeof(int));
        }
        for(int y=0;y<n;y++)
            uniq_path[0][y] = 1;
        for(int x=0;x<m;x++)
            uniq_path[x][0] = 1;
        return dpuniquePaths(uniq_path,m-1,n-1);
    }
发表于 2017-09-07 13:38:42 回复(0)
C/C++
xyxlil头像 xyxlil
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[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];
    }
};

编辑于 2017-03-10 12:47:00 回复(5)
已注销头像 已注销 
int uniquePaths(int m, int n) {
		vector<int> myvector(n,0);
		myvector[0] = 1;
		for (int i = 0; i <m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				myvector[j] += myvector[j - 1];
			}
		}
		return myvector[n - 1];
	}
动态规划 状态转移方程  F[i,j]=F[i-1,j]+F[i,j-1]
发表于 2016-03-19 15:40:04 回复(3)
C/C++
WZ_Dale头像 WZ_Dale
动态规划
    状态：
        子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的路径数
        F(i,j): 从(0,0)到达F(i,j)的路径数
    状态递推：
        F(i,j) = F(i-1,j) + F(i,j-1)
    初始化：
        特殊情况：第0行和第0列
        F(0,i) = 1
        F(i,0) = 1
    返回结果：
        F(m-1,n-1) 

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m <= 0 || n <= 0){
            return 0;
        }
        vector<vector<int>> F(m, vector<int>(n, 1));
        for(int i = 1; i < m; ++i){
            for(int j = 1; j < n; ++j){
                F[i][j] = F[i - 1][j] + F[i][j - 1];
            }
        }
        return F[m - 1][n - 1];
    }
};


发表于 2020-05-10 13:18:23 回复(0)
Java
詆調壹點头像 詆調壹點 
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];
	}
}

发表于 2017-03-24 21:43:46 回复(0)
thomas10011头像 thomas10011
动态规划，三行代码。
简历坐标系为起点(1, 1)，终点(m, n)。
到达m，n的路径是到达(m-1, n)的路径之和加上到达(m, n-1)的路径之和，当m或n为1时，说明到达了边界，只有一条路径。 
class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        // write code here
        if(m == 1 || n == 1)
            return 1;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
};


发表于 2021-01-14 21:01:54 回复(4)
提交观点

问题信息

动态规划
难度：
290条回答 32431浏览

热门推荐

通过挑战的用户

查看代码

相关试题

不同路径的数目(一)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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