欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-12 12:39:47
...

一、问题描述

给定一个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];
    }
};