62. Unique Paths ----M

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

 

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

 

Constraints:

• 1 <= m, n <= 100

A:

另外，其实，可以免掉recursive调用，直接在数组上来计算的。

----第二遍  Iterative way, using 2D array----

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

 利用一维数组  using 1D array 

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

第一个是recursively  调用，同时用一个数组，来记录已经用过的调用。

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        // DP
        int[][] pathNum = new int[m + 1][n + 1];// ignore the 0 row and col
        return recursivePath(pathNum, m, n);

    }

    private int recursivePath(int[][] pathNum, int row, int col) {
        if (pathNum[row][col] != 0) {
            return pathNum[row][col];
        } else {
            // else ,we need calculate them
            if (row == 1 && col == 1) {
                pathNum[1][1] = 1;
                return 1;
            }
            // now we can reduce their case
            int stepDown = 0;
            if (row >= 2) {
                stepDown = recursivePath(pathNum, row - 1, col);
                pathNum[row - 1][col] = stepDown;
            }
            int stepRight = 0;
            if (col >= 2) {
                stepRight = recursivePath(pathNum, row, col - 1);
                pathNum[row][col - 1] = stepRight;
            }
            return stepRight + stepDown;
        }
    }
}