LeetCode 第100热题 | 多维动态规划（一）

1 多维动态规划

当前的感知信息被表述为二维数组的形式。

2 62. 不同路径

题眼：“机器人每次仅能选择向下或向右移动一步”。

核心理念：将整体问题分解为多个子问题进行处理。

• 总体问题：从起点出发，到达第 i 行第 j 列的位置共有多少种不同路径
• 子问题一：从起点出发，到达第 i - 1 行第 j 列的位置共有多少种不同路径
• 子问题二：从起点出发，到达第 i 行第 j - 1 列的位置共有多少种不同路径
• 总体问题的解 = 子问题一的解 + 子问题二的解

思路解析图：如上图所示，到达第 1 行第 2 列位置的路径总数等于到达第 0 行第 2 列位置的路径数加上到达第 1 行第 1 列位置的路径数。同时，在设定边界条件时，应将边界格子的路径数设为 1，因为这些格子仅存在唯一的一条可行路径。

 class Solution {

    
 public:
    
     int uniquePaths(int m, int n) {
    
     vector<vector<int>> dp(m, vector