[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];
        }
    };