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?\

本题是从起点到终点向右向下走所有路径的条数，模型从小-》大，可以发现用动态规划当前模型可以使用比当前模型小的结果，M[i][j]表示当机器人位于i,j位置的时候到终点的路径条数，而induction rule = M[i+1][j] + M[i][j+1]， 这里的空间复杂度为O（n^2）

solution1:

class Solution {
public:
    int uniquePaths(int m, int n) {
        //sanity check
        if (m <0 || n < 0) return 0;
        if (m == 1 || n == 1) return 1;
        int M[m][n];
        //base case'
        M[m-1][n-1] = 0;
        for (int i = m-2; i >= 0; i--) {
            M[i][n-1] = 1;
        }
        for (int i = n-2; i >= 0; i--) {
            M[m-1][i] = 1;
        }
        for (int i = m-2; i >= 0; i--) {
            for (int j = n-2; j >= 0; j-- ) {
                M[i][j] = M[i+1][j] + M[i][j+1];
            }
        }
        return M[0][0];
    }
};
solution 2:
 通过第一种方法填表发现每一列或者每一行里面的值其实只依赖前面一列或者前面一行，所以只需要维护一个一维的数组就可以了，空间复杂度可以降到O（n)
 通过这个题目发现很多DP的题目，在空间复杂度上是可以降低的，O（n^2）->O(n), O(n)->O(1), 降低的标准在于dp里面的递推式的依赖值，大部分dp的空间复杂度都是可以降低的。
class Solution {
public:
    int uniquePaths(int m, int n) {
        //sanity check
        if (m == 0 || n == 0) return 0;
        vector<int> M(n,1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                M[j] += M[j-1];
            }
        }
        return M[n-1];
    }
};