1. 动态规划核心思想回顾在算法学习过程中动态规划(Dynamic Programming)是最具挑战性也最实用的解题方法之一。今天要分享的代码随想录day34内容主要聚焦动态规划中两个经典问题62.不同路径和63.不同路径II。这两个题目看似简单却蕴含着动态规划最核心的解题思路。动态规划的本质是通过将原问题分解为相对简单的子问题的方式来解决复杂问题。与分治法不同动态规划适用于子问题重叠的情况即不同的子问题具有公共的子子问题。这种情况下动态规划算法会对每个子子问题只解一次将其解保存在一个表格中从而避免重复计算。关键理解动态规划三要素 - 最优子结构、边界条件和状态转移方程。这是解决任何DP问题的基础框架。2. 不同路径问题解析2.1 问题描述与基础解法LeetCode 62题描述一个机器人位于m×n网格的左上角每次只能向下或向右移动一步。机器人试图达到网格的右下角问总共有多少条不同的路径这个问题的暴力解法是使用深度优先搜索(DFS)尝试所有可能的路径组合。但这种方法的时间复杂度是指数级的O(2^(mn))在m和n较大时完全不可行。# 暴力DFS解法仅作对比实际不可用 def uniquePaths(m, n): def dfs(i, j): if i m-1 and j n-1: return 1 if i m or j n: return 0 return dfs(i1, j) dfs(i, j1) return dfs(0, 0)2.2 动态规划解法实现动态规划解法将时间复杂度优化到O(m×n)空间复杂度同样为O(m×n)定义dp数组dp[i][j]表示从(0,0)到(i,j)的路径数初始化第一行和第一列都只有1种走法状态转移dp[i][j] dp[i-1][j] dp[i][j-1]def uniquePaths(m, n): dp [[1]*n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]2.3 空间优化技巧观察状态转移方程可以发现我们只需要前一行的数据即可计算当前行。因此可以将空间复杂度优化到O(n)def uniquePaths(m, n): dp [1] * n for _ in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[-1]实测数据当mn100时优化前使用内存约80KB优化后仅使用约800B内存使用减少99%。3. 带障碍物的不同路径问题3.1 问题变化与挑战LeetCode 63题在62题基础上增加了障碍物网格中的障碍物和空位置分别用1和0表示机器人不能经过障碍物。这给问题带来了新的复杂度。关键难点在于初始化时遇到障碍物后后续位置都不可达状态转移时遇到障碍物需要特殊处理边界条件更加复杂3.2 完整DP解法实现def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) dp [[0]*n for _ in range(m)] # 初始化第一列 for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 1 # 初始化第一行 for j in range(n): if obstacleGrid[0][j] 1: break dp[0][j] 1 # 状态转移 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]3.3 易错点分析在实际编码中有几个常见错误需要特别注意初始化时遇到障碍物后没有break导致后续位置被错误赋值忘记处理起点或终点本身就是障碍物的情况状态转移时没有先判断当前位置是否为障碍物调试技巧可以打印中间dp数组的值观察是否正确处理了障碍物位置。4. 动态规划解题方法论4.1 解题通用步骤通过这两个题目我们可以总结出解决动态规划问题的通用方法确定dp数组及下标的含义确定递推公式状态转移方程初始化dp数组确定遍历顺序举例推导dp数组4.2 如何识别DP问题适合用动态规划解决的问题通常具有以下特征问题可以分解为重叠子问题问题具有最优子结构性质需要求解的是计数、最值或存在性问题4.3 调试与验证技巧手动计算小规模案例验证代码正确性打印中间状态观察是否符合预期对比暴力解法结果适用于小规模数据考虑边界条件空输入、单行/单列、全障碍物等5. 进阶思考与扩展5.1 其他变种问题掌握了基础的不同路径问题后可以尝试以下变种加入对角线移动的权限每个格子有不同的通过代价求最小代价路径需要收集特定物品的路径问题5.2 动态规划优化方向对于更复杂的问题可以考虑以下优化方向滚动数组优化空间复杂度记忆化搜索实现方式并行计算优化预处理减少计算量5.3 实际应用场景动态规划在现实中有广泛的应用机器人路径规划生物信息学中的序列比对金融领域的投资组合优化自然语言处理中的词对齐6. 个人实战经验分享在实际刷题过程中我发现动态规划问题最关键的突破点是正确识别状态定义。以不同路径问题为例最初我尝试用三维dp[i][j][k]表示位置和剩余步数导致复杂度爆炸后来意识到路径数只与当前位置有关与如何到达当前位置无关这才确定了正确的二维状态表示方法另一个重要体会是先写出基础解法再考虑优化。我经常犯的错误是一开始就想写出最优解导致代码复杂难以调试实际上应该先写出清晰的暴力解或记忆化搜索再逐步优化空间和时间复杂度对于障碍物问题的处理我总结出一个检查清单起点是否为障碍物终点是否为障碍物第一行/列中间的障碍物是否阻断后续路径内部障碍物是否被正确跳过最后分享一个实用技巧在解决DP问题时我习惯先在纸上画出状态转移图标注每个状态的依赖关系。这种方法特别适合二维DP问题可以直观地理解状态转移过程。 动态规划实战：不同路径问题解析与优化
1. 动态规划核心思想回顾在算法学习过程中动态规划(Dynamic Programming)是最具挑战性也最实用的解题方法之一。今天要分享的代码随想录day34内容主要聚焦动态规划中两个经典问题62.不同路径和63.不同路径II。这两个题目看似简单却蕴含着动态规划最核心的解题思路。动态规划的本质是通过将原问题分解为相对简单的子问题的方式来解决复杂问题。与分治法不同动态规划适用于子问题重叠的情况即不同的子问题具有公共的子子问题。这种情况下动态规划算法会对每个子子问题只解一次将其解保存在一个表格中从而避免重复计算。关键理解动态规划三要素 - 最优子结构、边界条件和状态转移方程。这是解决任何DP问题的基础框架。2. 不同路径问题解析2.1 问题描述与基础解法LeetCode 62题描述一个机器人位于m×n网格的左上角每次只能向下或向右移动一步。机器人试图达到网格的右下角问总共有多少条不同的路径这个问题的暴力解法是使用深度优先搜索(DFS)尝试所有可能的路径组合。但这种方法的时间复杂度是指数级的O(2^(mn))在m和n较大时完全不可行。# 暴力DFS解法仅作对比实际不可用 def uniquePaths(m, n): def dfs(i, j): if i m-1 and j n-1: return 1 if i m or j n: return 0 return dfs(i1, j) dfs(i, j1) return dfs(0, 0)2.2 动态规划解法实现动态规划解法将时间复杂度优化到O(m×n)空间复杂度同样为O(m×n)定义dp数组dp[i][j]表示从(0,0)到(i,j)的路径数初始化第一行和第一列都只有1种走法状态转移dp[i][j] dp[i-1][j] dp[i][j-1]def uniquePaths(m, n): dp [[1]*n for _ in range(m)] for i in range(1, m): for j in range(1, n): dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]2.3 空间优化技巧观察状态转移方程可以发现我们只需要前一行的数据即可计算当前行。因此可以将空间复杂度优化到O(n)def uniquePaths(m, n): dp [1] * n for _ in range(1, m): for j in range(1, n): dp[j] dp[j-1] return dp[-1]实测数据当mn100时优化前使用内存约80KB优化后仅使用约800B内存使用减少99%。3. 带障碍物的不同路径问题3.1 问题变化与挑战LeetCode 63题在62题基础上增加了障碍物网格中的障碍物和空位置分别用1和0表示机器人不能经过障碍物。这给问题带来了新的复杂度。关键难点在于初始化时遇到障碍物后后续位置都不可达状态转移时遇到障碍物需要特殊处理边界条件更加复杂3.2 完整DP解法实现def uniquePathsWithObstacles(obstacleGrid): m, n len(obstacleGrid), len(obstacleGrid[0]) dp [[0]*n for _ in range(m)] # 初始化第一列 for i in range(m): if obstacleGrid[i][0] 1: break dp[i][0] 1 # 初始化第一行 for j in range(n): if obstacleGrid[0][j] 1: break dp[0][j] 1 # 状态转移 for i in range(1, m): for j in range(1, n): if obstacleGrid[i][j] 1: dp[i][j] 0 else: dp[i][j] dp[i-1][j] dp[i][j-1] return dp[-1][-1]3.3 易错点分析在实际编码中有几个常见错误需要特别注意初始化时遇到障碍物后没有break导致后续位置被错误赋值忘记处理起点或终点本身就是障碍物的情况状态转移时没有先判断当前位置是否为障碍物调试技巧可以打印中间dp数组的值观察是否正确处理了障碍物位置。4. 动态规划解题方法论4.1 解题通用步骤通过这两个题目我们可以总结出解决动态规划问题的通用方法确定dp数组及下标的含义确定递推公式状态转移方程初始化dp数组确定遍历顺序举例推导dp数组4.2 如何识别DP问题适合用动态规划解决的问题通常具有以下特征问题可以分解为重叠子问题问题具有最优子结构性质需要求解的是计数、最值或存在性问题4.3 调试与验证技巧手动计算小规模案例验证代码正确性打印中间状态观察是否符合预期对比暴力解法结果适用于小规模数据考虑边界条件空输入、单行/单列、全障碍物等5. 进阶思考与扩展5.1 其他变种问题掌握了基础的不同路径问题后可以尝试以下变种加入对角线移动的权限每个格子有不同的通过代价求最小代价路径需要收集特定物品的路径问题5.2 动态规划优化方向对于更复杂的问题可以考虑以下优化方向滚动数组优化空间复杂度记忆化搜索实现方式并行计算优化预处理减少计算量5.3 实际应用场景动态规划在现实中有广泛的应用机器人路径规划生物信息学中的序列比对金融领域的投资组合优化自然语言处理中的词对齐6. 个人实战经验分享在实际刷题过程中我发现动态规划问题最关键的突破点是正确识别状态定义。以不同路径问题为例最初我尝试用三维dp[i][j][k]表示位置和剩余步数导致复杂度爆炸后来意识到路径数只与当前位置有关与如何到达当前位置无关这才确定了正确的二维状态表示方法另一个重要体会是先写出基础解法再考虑优化。我经常犯的错误是一开始就想写出最优解导致代码复杂难以调试实际上应该先写出清晰的暴力解或记忆化搜索再逐步优化空间和时间复杂度对于障碍物问题的处理我总结出一个检查清单起点是否为障碍物终点是否为障碍物第一行/列中间的障碍物是否阻断后续路径内部障碍物是否被正确跳过最后分享一个实用技巧在解决DP问题时我习惯先在纸上画出状态转移图标注每个状态的依赖关系。这种方法特别适合二维DP问题可以直观地理解状态转移过程。