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).

http://www.lintcode.com/en/problem/unique-paths/

Discussion

比较简单的动态规划问题。f[i][j]表示从i到j的path数，只能从上方或者左方到达。

Solution

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        // wirte your code here
        if(m==0 || n==0)
            return 0;
        vector<vector<int> > f(m, vector<int>(n, 0));
        for(int i=0; i<m; i++) {
            f[i][0] = 1;
        }
        for(int i=0; i<n; i++) {
            f[0][i] = 1;
        }
        for(int i=1; i<m; i++) {
            for(int j=1; j<n; j++) {
                f[i][j] = f[i-1][j] + f[i][j-1];
            }
        }
        return f[m-1][n-1];
    }
};

改成滚动数组加动规. 画个图什么都明白了。

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        // wirte your code here
        if(m<=0 || n<=0)
            return 0;
        vector<int> f(n, 1);
        for(int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
               f[j] = f[j] + f[j-1];
            }
        }
        return f[n-1];
    }
};

越是简单的问题越要想的多一些。。。比如这个，用动规的思路，写递归，非常非常的简洁。只能从上方或者左方到达，所以结果是uniquePaths(m-1, n) + uniquePaths(m, n-1);,再注意收敛条件就行了。

class Solution {
public:
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    int uniquePaths(int m, int n) {
        // wirte your code here
        if(m==1 && n==1) return 1;
        if(m<1 || n<1) return 0;

        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
};