动态规划的状态转移：从问题到状态转移方程的过程

动态规划通过拆分问题、存储中间结果避免重复计算，适用于有重叠子问题和最优子结构的场景。其核心是“状态转移”，即不同阶段状态间的推导关系。以爬楼梯为例：定义`dp[i]`为爬到第`i`级台阶的方法数，转移方程为`dp[i] = dp[i-1] + dp[i-2]`，初始条件`dp[0]=1`（0级台阶1种方法）、`dp[1]=1`（1级台阶1种方法）。另一拓展例子（零钱兑换）中，`dp[i]`表示凑`i`元的最少硬币数，转移方程为`dp[i] = min(dp[i-coin]+1)`（`coin`为可用面额），初始条件`dp[0]=0`，其余为无穷大。初学者需掌握“定义状态→找转移关系→写方程”，通过练习熟悉状态转移思维。动态规划本质是“空间换时间”，状态转移方程是连接中间结果的桥梁。