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 pZ喎?/kf/ware/vc/" target="_blank" class="keylink">vc3NpYmxlIHVuaXF1ZSBwYXRocyBhcmUgdGhlcmU/PC9wPgo8cD4KTm90ZTogbSBhbmQgbiB3aWxsIGJlIGF0IG1vc3QgMTAwLjwvcD4KPGg0PqG+y7zCt6G/PC9oND4KPHA+yehzW2ldW2pdIM6qtNPG8LXjtb2jqGksaqOpzrvWw7SmtcTCt762yv2hozwvcD4KPHA+zai5/bfWzva1w7W9o7q12tK70NCjrLXa0rvB0La8zqoxPC9wPgo8cD61vcbky/vOu9bDtKajqGksaqOpo7q1vbTvzrvWw6OoaSxqo6nWu8TctNPJz8Pmu/LV39fzw+a5/cC0o6zS8rTLvva2qLW9zrvWw6OoaSxqo6m1xMK3vrbK/dPJtb2078nPw+bOu9bDo6hpLTEsaqOptcTCt762yv26zbW9tO/X88PmzrvWw6OoaSxqLTGjqbXEwre+tsv5vva2qLXEoaM8L3A+CjxwPte0zKzXqtLGt72zzKO6PC9wPgo8cD5zW2ldW2pdID0gc1tpLTFdW2pdICYjNDM7IHNbaV1bai0xXTwvcD4KPHA+yrG85Li01NO2yKO6TyhuXjIpICC/1bzkuLTU07bIo7pPKG5eMik8L3A+CjxoND6hvrT6wuuhvzwvaDQ+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;"> /*------------------------------------
* 日期:2015-02-03
* 作者:SJF0115
* 題目: 62.Unique Paths
* 網址:https://oj.leetcode.com/problems/unique-paths/
* 結果:AC
* 來源:LeetCode
* 博客:
---------------------------------------*/
#include 使用空間輪轉的思路,節省空間。 狀態轉移方程: 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];
}
};