算法
无后效性是动态规划的核心特性之一，简单来说可以理解为：某个阶段的状态一旦确定，后续的决策不会改变这个状态的历史。具体表现为：
未来与过去无关
当前状态包含了解决问题所需的全部信息，后续决策只需要基于当前状态，不需要追溯状态是如何形成的。状态是时间/阶段的“快照”
例如走迷宫时，若你站在坐标 (x,y)，下一步的路径选择只取决于当前位置，与你之前是从左边还是上边走到这里的路径无关。
📌 典型例子
最短路径问题：
若从 A 到 C 的最短路径经过 B，那么从 B 到 C 的最短路径只取决于 B 的位置，与如何从 A 到 B 无关。斐波那契数列：
f(n) = f(n-1) + f(n-2)，计算f(n)时只需知道前两项的值，不需要知道它们是如何计算的。
❌ 违反无后效性的情况
例如在迷宫问题中，若规定某些格子经过次数不能超过 k 次，此时状态不仅要记录当前位置，还要记录历史经过次数，后续决策会受过去路径影响，此时无法直接用传统动态规划。
动态规划的本质
无后效性允许我们将问题分解为可缓存的子问题，通过记录每个状态的最优解（如 dp[i][j]），避免重复计算，这是动态规划高效的关键。
我将从状态转移方程开始讲起，再深入探讨动态规划的本质，最后总结动态规划解决问题的核心逻辑。
一、状态转移方程
状态转移方程是动态规划的核心，它定义了不同状态之间的递推关系。通过数学公式描述如何从已知子问题的解推导出当前问题的解。
📌 核心公式：
[
\text{当前状态} = f(\text{前一或多个子状态})
]
🌰 例子：
斐波那契数列
[
dp[n] = dp[n-1] + dp[n-2]
]- 状态定义：
dp[n]表示第n项的值 - 转移逻辑：当前项等于前两项之和
- 状态定义：
背包问题
[
dp[i][w] = \max(dp[i-1][w], \ dp[i-1][w - w_i] + v_i)
]- 状态定义：
dp[i][w]表示前i个物品在容量w下的最大价值 - 转移逻辑：选或不选第
i个物品的两种情况取最大值
- 状态定义：
二、动态规划的本质
动态规划的本质是对递归问题的优化，核心思想是用空间换时间，通过以下三要素实现：
1. 最优子结构 (Optimal Substructure)
问题的最优解包含子问题的最优解。
- 例如：最短路径中，从 A→C 的最优路径必须包含中间点 B→C 的最优路径。
2. 重叠子问题 (Overlapping Subproblems)
子问题被重复计算多次，通过缓存（如 dp 表）避免重复计算。
- 例如：计算斐波那契数列时，
f(3)会被f(4)和f(5)重复调用。
3. 状态转移方程 (State Transition Equation)
定义状态之间的递推关系，是动态规划算法的“发动机”。
三、动态规划的思维框架
定义状态
确定问题需要记录的变量（如背包问题中的物品序号和剩余容量）。- 例如：
dp[i][j]表示走到网格(i,j)的最小路径和。
- 例如：
找到转移关系
推导如何从已知状态计算新状态（核心难点）。- 例如：网格问题中，
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
- 例如：网格问题中，
初始化边界
处理初始状态的赋值（如第一行或第一列的路径和）。确定计算顺序
确保在计算当前状态时，所需子状态已被计算（如从左到右、从底到顶）。
四、动态规划的“灵魂”是什么？
动态规划的灵魂在于将问题抽象为状态空间的递推，通过以下步骤：
- 识别关键变量 → 2. 构建状态定义 → 3. 找到递推规则 → 4. 利用历史状态推导未来。
🌰 例子对比：
- 暴力递归：计算斐波那契数列时，时间复杂度为 (O(2^n))，大量重复计算。
- 动态规划：通过
dp数组存储中间结果，时间复杂度降为 (O(n))。
五、适用场景
动态规划适合解决两类问题：
- 最优化问题：求最大值、最小值（如背包问题、最短路径）。
- 计数问题：求方案总数（如爬楼梯的不同方式数）。
总结：动态规划的本质
动态规划是一种通过状态定义和递推关系，将复杂问题分解为简单子问题，并通过缓存子问题的解避免重复计算的高效算法设计范式。其核心在于：
- 状态转移方程：定义问题分解的逻辑
- 无后效性：保证状态可以被独立缓存
- 最优子结构：允许局部最优推导全局最优
理解这三点，就能抓住动态规划的精髓 ✅。