【LeetCode】62. Unique Paths解法及注释

本是古典何须时尚 2022-07-26 06:03 151阅读 0赞

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

![robot_maze.png][]

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

Note: m and n will be at most 100.

【分析】

题目规定只能向右和向下两种行进方式，从起点到终点需要行进(m-1+n-1)步，向右行进和向下行进的步数是确定的，只是一个顺序问题，本质上就是一个高中数学里的排列组合问题：总共有(m+n-2)个位置，将向右行进的(n-1)个位置插入其中（或者将向下行进的(m-1)个位置插入其中）：

![Center][]

但是按照这个数学算式求解复杂度比较高，特别是题目规定 0=<m,n<=100，这样需要做多次乘法，效率不高。

针对本题，更合适的方法是“动态规划”方法：欲到达终点position\[m\]\[n\]，必先达到position\[m-1\]\[n\]或者position\[m\]\[n-1\]，如是，到达position\[m-1\]\[n\]和position\[m\]\[n-1\]的路径数之和就是到达position\[m\]\[n\]的路径总数，我们可通过两重循环解决问题：

【解法及注释】

class Solution {
    public:
        int uniquePaths(int m, int n) {
            
            vector<vector<int>> path(m, vector<int>(n, 1));//初始化路径矩阵中的每一格为1，相当于行进步长
            for(int i=1; i<m; i++)//初始位置为path[0][0]，故循环起始为1
            {
                for(int j=1; j<n; j++)
                {
                    path[i][j] = path[i-1][j] + path[i][j-1];
                }
            }
            return path[m-1][n-1];
    
        }
    };

[robot_maze.png]: http://leetcode.com/wp-content/uploads/2014/12/robot_maze.png
[Center]: /images/20220724/0afdf935df954f83b73b57d990ac5f46.png