LeetCode 热题 HOT 100 （2）1

【LeetCode 热题 HOT 100（2）】系列主要涵盖了多个与动态规划相关的编程题目。这里我们分析其中三个题目：62. 不同路径、64. 最小路径和以及170. 爬楼梯。 1. **62. 不同路径** 这是一个典型的动态规划问题，目标是从网格的左上角走到右下角，每一步只能向下或向右移动。状态表示为 `f[i][j]`，它表示从起点 `(0,0)` 到达 `(i,j)` 的不同路径数量。初始条件是 `f[0][0] = 1`，因为只有一种方式到达起始位置。状态转移方程是 `f[i][j] = f[i-1][j] + f[i][j-1]`，这意味着到达 `(i,j)` 可以通过从 `(i-1,j)` 或 `(i,j-1)` 走来。答案是 `f[m-1][n-1]`，即到达网格右下角的不同路径数。 ```cpp class Solution { public: int uniquePaths(int m, int n) { if(!n || !m) return 0; vector>f(m + 1, vector(n + 1)); f[0][0] = 1; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++){ if(!i && !j) continue; if(i) f[i][j] += f[i - 1][j]; if(j) f[i][j] += f[i][j - 1]; } return f[m - 1][n - 1]; } }; ``` 2. **64. 最小路径和** 类似于62题，但这次我们要找的是从左上角到右下角的最小路径和，每步仍然只能向下或向右。状态表示为 `f[i][j]`，它表示到达 `(i,j)` 的最小路径和。初始条件是 `f[0][0] = grid[0][0]`，因为路径和等于起始格子的值。状态转移方程变为 `f[i][j] = min(f[i - 1][j] + grid[i][j], f[i][j - 1] + grid[i][j])`，选择路径和较小的转移。最终答案同样是 `f[m-1][n-1]`。 ```cpp class Solution { public: int minPathSum(vector>& grid) { int n = grid.size(), m = grid[0].size(); vector> f(n + 1, vector(m + 1, INT_MAX)); f[0][0] = grid[0][0]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){ if(!i && !j) continue; if(i) f[i][j] = min(f[i - 1][j] + grid[i][j], f[i][j]); if(j) f[i][j] = min(f[i][j - 1] + grid[i][j], f[i][j]); } return f[m - 1][n - 1]; } }; ``` 3. **170. 爬楼梯** 该题目的动态规划解法基于斐波那契数列。问题是要找到上n阶楼梯的不同方式数。可以定义数组 `f[i]` 表示上 `i` 阶台阶的方案数，其中 `f[1] = 1`（单步上）和 `f[2] = 1`（两步上）。状态转移方程是 `f[i] = f[i-1] + f[i-2]`，表示上 `i` 阶楼梯的方式数等于上 `i-1` 阶和上 `i-2` 阶的方式数之和。 以上三个题目都是经典的动态规划问题，它们的核心在于理解问题的本质，定义适当的状态表示，并找出状态之间的转移关系。在实现过程中，通常需要使用二维数组来存储中间结果，以便在计算当前状态时能引用到之前的状态。时间复杂度通常与网格的行数和列数成正比，即 O(m * n)，对于每个问题都需要考虑边界条件并正确初始化状态数组。