LeetCode OJ:Unique Paths(唯一路径)
2024-08-24 01:03:16
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
题目的意思就是给你一个m*n网格,求从左上角到右下角的路径条数即可,用dp很容易解决,推到式为res[i][j] = res[i - 1][j] + res[i][j - 1]。意思就是到一个特定点的路径条数是到其左侧或者上侧点的路径条数的总和。
代码如下:
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int> > ans(m, vector<int>(n, ));
for(int i = ; i < m; ++i)
ans[i][] = ;
for(int j = ; j < n; ++j)
ans[][j] = ; for(int i = ; i < m; ++i){
for(int j = ; j < n; ++j){
ans[i][j] = ans[i - ][j] + ans[i][j - ];
}
}
return ans[m - ][n - ];
}
};
还有一种方法是使用dfs来实现,但是数大了就容易超时,这题的本意可能就是dfs,这里把代码放上:
class Solution {
public:
int uniquePaths(int m, int n) {
times = ;
maxHor = m, maxVer = n;
dfs(,);
return times;
}
void dfs(int hor, int ver){
if((hor == maxHor - ) && (ver = maxVer - ))
times++;
else{
if(hor + < maxHor) //注意这里不是while
dfs(hor + , ver);
if(ver + < maxVer)
dfs(hor, ver + );
}
}
private:
int times;
int maxHor;
int maxVer;
};
java版本如下所示,dp实现:
public class Solution {
public int uniquePaths(int m, int n) {
if(m == 0 || n == 0)
return 0;
int [][] grid = new int [m][n];
for(int i = 0; i < m; ++i){
grid[i][0] = 1;
}
for(int i = 0; i < n; ++i){
grid[0][i] = 1;
}
for(int i = 1; i < m; ++i){
for(int j = 1; j < n; ++j){
grid[i][j] = grid[i-1][j] + grid[i][j-1];
}
}
return grid[m-1][n-1];
}
}
最新文章
- 参数table_open_cache
- CSS的Hack技术
- 要当好JavaScript程序员:5个debug技巧
- 【position也可以很复杂】当弹出层遇上了鼠标定位(上)
- Virtualbox虚拟机安装CentOS6.5图文详细教程
- LICEcap GIF 屏幕录制工具
- listView异步处理图片下载缓存
- HDU 1199 - Color the Ball 离散化
- 作死上CODEVS,青铜题
- python--Selectors模块/队列
- java的8种基础类型
- form表单提交数据,页面必定会刷新,ajax提交数据不会刷新,做到悄悄提交,多选删除,ajax提交实例
- php-kafka
- Luogu P2880 [USACO07JAN]平衡的阵容Balanced Lineup (ST表模板)
- (第7篇)灵活易用易维护的hadoop数据仓库工具——Hive
- lua -- 所有UI组件的基类
- EntityFrameworkCore概览
- 小程序开发 绑定自定义数据data- 及JS获取
- input文字颜色、光标颜色
- 对一个前端使用AngularJS后端使用ASP.NET Web API项目的理解(1)