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

Note: m and n will be at most 100.

Example 1:

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 -> Right -> Down
2.Right -> Down -> Right
3.Down -> Right -> Right

Example 2:

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

0、题目分析

这是一道简单的动态规划题目，分析题目发现机器人每次只能向右或者向下走，设到某一个点的路径数目为path[i][j]，则

path[i][j] = path[i-1][j] + path[i][j-1]

从而我们得到实现动态规划的递推表达式

另外当i==0 || j==0时，path[i][j] == 1

1、代码实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        int map[m][n] = {};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) map[i][j] = 1;
                else map[i][j] = map[i-1][j] + map[i][j-1];
            }
        }
        return map[m-1][n-1];
    }
};

2、改进

经过进一步分析发现，其实我们没必要储存每一个点的路径数，因为我们只是想要最后一个位置的路径数，所以

path[j] = path[j] + path[j-1]

这样就改进了空间复杂度，从O(m*n)下降为O(n)

代码实现：

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

参考资料：leetcode 62. Unique Paths-唯一路径|动态规划