Unique Paths

Description

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?

Notice
m and n will be at most 100.

Example  
[1,1 1,2 1,3 1,4 1,5 1,6 1,7]
[2,1                        ]
[3,1                     3,7]
Above is a 3 x 7 grid. How many possible unique paths are there?

Link

Lintcode_ladder

Method

1. Dp, considering the boundary.
2. x

Example

1. 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
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j == 1) {
                    dp[i][j] = 1;
                } else if (i == 1) {
                    dp[i][j] =1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

Similar problems

x

Tags

x