首页 > 代码库 > [LeetCode]62.Unique Paths
[LeetCode]62.Unique Paths
【题目】
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?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
【思路】
设s[i][j] 为从起点到（i,j）位置处的路径数。
通过分析得到：第一行，第一列都为1
到其他位置处（i,j）：到达位置（i,j）只能从上面或者左面过来，因此决定到位置（i,j）的路径数由到达上面位置（i-1,j）的路径数和到达左面位置（i,j-1）的路径所决定的。
状态转移方程：
s[i][j] = s[i-1][j] + s[i][j-1]
时间复杂度：O(n^2) 空间复杂度：O(n^2)
【代码】
/*------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 题目: 62.Unique Paths
* 网址：https://oj.leetcode.com/problems/unique-paths/
* 结果：AC
* 来源：LeetCode
* 博客：
---------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
class Solution {
public:
int uniquePaths(int m, int n) {
int s[m][n];
for(int i = 0;i < m;++i){
for(int j = 0;j < n;++j){
if(i == 0|| j == 0){
s[i][j] = 1;
}//if
else{
s[i][j] = s[i-1][j] + s[i][j-1];
}//esle
}//for
}//for
return s[m-1][n-1];
}
};
int main(){
Solution s;
int m = 3;
int n = 4;
int result = s.uniquePaths(m,n);
// 输出
cout<<result<<endl;
return 0;
}
【思路二】
使用空间轮转的思路，节省空间。
状态转移方程：
s[j] = s[j] + s[j-1]
时间复杂度：O(n^2) 空间复杂度：O(n)
【代码二】
/*------------------------------------
* 日期：2015-02-03
* 作者：SJF0115
* 题目: 62.Unique Paths
* 网址：https://oj.leetcode.com/problems/unique-paths/
* 结果：AC
* 来源：LeetCode
* 博客：
---------------------------------------*/
class Solution {
public:
int uniquePaths(int m, int n) {
int s[n];
// 第一行全为1
for(int i = 0;i < n;++i){
s[i] = 1;
}//for
// 从第二行开始
for(int i = 1;i < m;++i){
// 第i行第j个格
for(int j = 1;j < n;++j){
s[j] = s[j] + s[j-1];
}//for
}//for
return s[n-1];
}
};
[LeetCode]62.Unique Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。