Unique-Paths

发表于 | 更新于：

题目地址

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?

img

  Above is a 3 x 7 grid. How many possible unique paths are there?

  Note: m and n will be at most 100.

解题思路

  一看到这题就想到无脑递归，但是最后看了看，觉得很有可能会 TEL ，所以放弃选择了 DP 。我们可以简单推出 Start （DP[0][0]） 到 Finish 的路径个数等于他的下边方格（DP[1][0]）和右边方格（DP[0][1]）之和。继续往下推也是这个道理，所以最后有递推公式：

dp[i][j] = dp[i+1][j] + dp[i][j+1];

解题代码【.CPP】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m , vector<int>(n , 0));
        dp[m-1][n-1] = 1;
        for (int i = m-1; i >= 0; --i) {
            for (int j = n-1; j >= 0; --j) {
                if (i+1 < m) dp[i][j] += dp[i+1][j];
                if (j+1 < n) dp[i][j] += dp[i][j+1];
            }
        }
        return dp[0][0];
    }
};
0%