leetcode 62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3
输出: 28

动态规划，设二维数组v_i，则每个值v_i[i][j]代表了第i行第j列有多少方法可以走到

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> v_i(n, vector<int>(m, 1));
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                v_i[i][j] = v_i[i-1][j]+v_i[i][j-1];
            }
        }
        return v_i[n-1][m-1];
    }
};

方法二，通过记忆数组递归

class Solution {
public:
    int dp(int n, int m){
        if(n-1<0 || m-1<0)return 0;
        if(vi[n-1][m-1]!=0) return vi[n-1][m-1];
        int left = dp(n, m-1);
        int up = dp(n-1, m);
        vi[n-1][m-1] = left+up;
        return vi[n-1][m-1];
    }
    int uniquePaths(int m, int n) {
        vector<int> v_i;
        //初始化这个矩阵，第一行和第一列都置为1
        for (int i = 0; i < n; ++i) {
            v_i.clear();
            for (int j = 0; j < m; ++j) {
                if(i==0 or j==0) v_i.push_back(1);
                else v_i.push_back(0);
            }
            vi.push_back(v_i);
        }
        dp(n, m);
        return vi[n-1][m-1];
    }
private:
    vector<vector<int>> vi;
};