LeetCode动态规划解题策略：不同路径与最小路径和

这篇资源主要介绍了两个LeetCode热门题目——62. 不同路径和64. 最小路径和，这两个都是经典的动态规划问题。 对于62. 不同路径，问题的核心在于从网格的左上角(0,0)走到右下角(n-1, m-1)的每一步只能向右或向下移动。使用动态规划的方法，可以定义一个二维数组f[i][j]，表示到达(i, j)位置的不同路径数。初始条件是f[0][0] = 1，因为从(0,0)到(0,0)只有一种路径。状态转移方程为f[i][j] = f[i-1][j] + f[i][j-1]，表示到达(i, j)的路径数是来自上方(i-1, j)的路径数加上来自左边(i, j-1)的路径数。最后，答案是f[n-1][m-1]。 对于64. 最小路径和，问题的设定类似，但需要求的是从左上角到右下角的最小路径和，每一步同样只能向右或向下，但每个格子都有一个非负整数作为代价。这次的状态表示为f[i][j]，表示到达(i, j)的最小路径和。初始条件是f[0][0] = grid[0][0]，其他位置初始化为正无穷大。状态转移方程为f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]，意味着到达(i, j)的最小路径和是来自上方或左侧路径和较小者加上当前位置的代价。最终答案同样是f[n-1][m-1]。 在C++代码实现中，对于62. 不同路径，定义了一个名为Solution的类，其中包含一个名为uniquePaths的公共成员函数，该函数接受两个整数m和n，返回不同路径的数量。使用二维向量f来存储状态，通过双重循环进行状态转移。对于64. 最小路径和，虽然没有给出完整的C++代码，但根据问题描述，可以推断出类似的解决方案，只是状态转移方程会涉及到最大值而不是相加。 两题的时间复杂度都是O(m * n)，因为每个格子的状态都需要更新一次，其中m和n分别代表网格的行数和列数。空间复杂度也是O(m * n)，用于存储状态数组。这两个问题都是动态规划的典型应用，通过自底向上的方式解决，避免了重复计算。