【LeetCode62 Unique Paths】动态规划计算路径

一、问题描述

给定一个m*n的方格，起始点为方格的最左上方，终点为方格的最右下方，一个机器人只能向下以及向右移动，需要求出机器人从起始点到终点一共有多少种不重复的路径。问题的输入为方格的长度m以及宽度n，输出为不同路径的数量。

二、思路分析

这道题用动态规划的方法非常简单，计算出机器人从起点开始到方格内每一个格子的不同路径数，并将路径数量保存到一个相同大小的m*n的矩阵中M，那么我们只需要输出终点所对应的矩阵值即可。对于路径中的每一个方格，机器人只能经过方格上方或者方格左侧从而到达方格，对应于矩阵M，我们就可以很清晰的得到M[i][j] = M[i-1][j]+M[i][j-1]，因为方格最上方以及方格最左侧均只有一条路径到达，因此又有M[0][j] = 1以及M[i][0] = 1，其中i,j表示m,n以内的任一数字。根据这两个公式，我们可以推断出机器人到达每一个方格的路径数，即可以得到完整的矩阵M值，输出M[m-1][n-1]即可。

三、代码实现

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