刷题62. Unique Paths
2024-09-07 01:14:43
一、题目说明
题目62. Unique Paths，在一个m*n矩阵中，求从左上角Start到右下角Finish所有路径。其中每次只能向下、向右移动。难度是Medium！
二、我的解答
这个题目读读题目，理解后不难。定义一个dp[m][n]，初始化最后一列为1，最后一行为1，然后循环计算到dp[0][0]就可以了。
代码如下：
class Solution{
public:
int uniquePaths(int m,int n){
vector<vector<int>> dp(m,vector<int>(n,0));
//最后一行初始化为1
for(int i=0;i<n;i++){
dp[m-1][i] = 1;
}
//最后一列初始化为1
for(int i=0;i<m;i++){
dp[i][n-1] = 1;
}
for(int t=n-2;t>=0;t--){
for(int k=m-2;k>=0;k--){
dp[k][t] = dp[k+1][t]+dp[k][t+1];
}
}
return dp[0][0];
}
};
性能如下：
Runtime: 4 ms, faster than 56.78% of C++ online submissions for Unique Paths.
Memory Usage: 8.8 MB, less than 32.81% of C++ online submissions for Unique Paths.
三、优化措施
其他没有看到更好的解答，递归，回溯，都比较复杂。
最新文章
- 得到APP【每天听本书】微信交流群（每天更新）
- kendo ui 富文本编辑控件 Editor 实现本地上传图片，并显示
- js循环添加事件的问题
- centos 安装gcc时，出错：Found 10 pre-existing rpmdb problem(s), 'yum check' output follows:
- Asp文件锁定脚本
- Android平台的开发环境的发展演变
- 用Editplus开发HTML
- 使用Redis来实现LBS的应用
- android tablelayout 显示图片
- openfire控制台登录不了的解决
- mysql锁表机制及相关优化
- ajax-Ajax试题
- MsSQL的游标的综合运用
- [hadoop转载]tearsort
- 第003篇 深入体验C#项目开发(二)
- AJAX入门——工作原理
- Android 窗口全屏
- Mac效率：配置Alfred web search
- MVC5中使用Log4Net
- Eclipse导入文件识别不了jsp怎么办