动态规划是解决复杂问题的一种常用方法，它通过拆分问题，存储中间结果，避免重复计算，从而提高效率。而“状态转移”是动态规划的核心环节，它描述了问题中不同阶段的状态之间如何相互影响、相互推导。对于初学者来说，理解如何从问题本身一步步推导出状态转移方程，是掌握动态规划的关键。
一、动态规划与状态转移的核心思想¶
动态规划通常用于解决具有重叠子问题和最优子结构的问题。例如，求斐波那契数列、爬楼梯、零钱兑换等。其核心在于：将复杂问题分解为多个简单的子问题，通过存储子问题的解（即“状态”），避免重复计算，最终推导出原问题的解。
状态转移是连接这些子问题解的“桥梁”。它描述了：当前状态如何由前一个或多个状态推导而来。
二、从问题到状态转移方程的步骤（以“爬楼梯”为例）¶
我们以“爬楼梯问题”作为具体例子，详细拆解“从问题到状态转移方程”的过程：
问题：假设你需要爬n级台阶，每次可以爬1级或2级，问有多少种不同的方法？
步骤1：明确问题，识别子问题¶
要解决“n级台阶的方法数”，观察发现：
- 最后一步只能是从n-1级爬1级，或从n-2级爬2级（最优子结构）。
- 因此，方法数 = 爬到n-1级的方法数 + 爬到n-2级的方法数（重叠子问题，如n=3时，n-1=2和n-2=1会重复计算）。
步骤2：定义状态¶
设dp[i]表示“爬到第i级台阶的方法数”。
- dp[i]是对“第i级台阶”这个阶段的量化描述，是我们需要计算的核心。
步骤3：推导状态转移方程¶
根据步骤1的分析，爬到第i级台阶的方法数，由两种情况叠加而成：
- 从i-1级爬1级：方法数为dp[i-1]；
- 从i-2级爬2级：方法数为dp[i-2]。
因此，状态转移方程为：
dp[i] = dp[i-1] + dp[i-2]
步骤4：确定初始条件和边界¶
状态转移需要“起点”，即最基础的状态值：
- dp[0] = 1（定义“0级台阶”为1种方法，作为递推起点）；
- dp[1] = 1（1级台阶只有1种方法：直接爬1级）。
步骤5：计算结果¶
有了状态转移方程和初始条件，即可逐步计算：
- dp[2] = dp[1] + dp[0] = 1 + 1 = 2（2级台阶：1+1或2）；
- dp[3] = dp[2] + dp[1] = 2 + 1 = 3（3级台阶：1+1+1、1+2、2+1）；
- 以此类推，dp[n]即为n级台阶的方法数。
三、另一个例子：零钱兑换问题（拓展）¶
问题：给定硬币面额[1,2,5]，总金额n，求凑出总金额最少需要多少枚硬币？若无法凑出，返回-1。
步骤1：定义状态¶
设dp[i]表示“凑出金额i所需的最少硬币数”。
步骤2：推导转移方程¶
要凑出金额i，最后一步可用任意面额coin，此时前面金额为i-coin，因此：
dp[i] = min(dp[i-coin] + 1)（若i >= coin且dp[i-coin]存在）。
步骤3：初始条件¶
dp[0] = 0（金额0无需硬币）；- 其他金额初始化为无穷大（表示“未凑出”）。
步骤4：计算结果（以n=5为例）¶
dp[0] = 0；dp[1] = dp[0] + 1 = 1（用1枚1元）；dp[2] = min(dp[1]+1, dp[0]+1) = 1（用1枚2元）；dp[5] = min(dp[4]+1, dp[3]+1, dp[0]+1) = 1（用1枚5元）。
四、初学者的关键总结¶
- 定义状态是基础：用
dp[i]清晰描述问题的阶段（如“凑出金额i”“爬到台阶i”）。 - 转移方程是核心：通过分析“最后一步如何到达当前状态”，找到状态间的依赖关系（如
dp[i] = dp[i-1] + dp[i-2]）。 - 初始条件不可少：从最基础的状态值（如
dp[0]）开始递推，避免推导时出错。 - 多练习积累经验：通过爬楼梯、零钱兑换、最长递增子序列等问题，逐步熟悉状态转移的思维。
动态规划的本质是“用空间换时间”，通过存储中间结果避免重复计算，而状态转移方程就是连接这些结果的桥梁。只要掌握“定义状态→找转移关系→写方程”的三步法，就能逐步攻克动态规划的核心！