[LeetCode]62.Unique Paths

【题目】

A robot is located at the top-left corner of amxngrid (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:mandnwill 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];
        }
    };