状态转移方程 是动态规划问题中的核心概念，它描述了问题从一种状态到另一种状态的转化关系。形象地说，就是“如何从已知的结果推出未知的结果”。
什么是状态转移方程？
- 状态： 在动态规划问题中，状态通常代表子问题的一个解或部分解。
- 转移： 状态之间的转换，即从一个子问题的解推导出另一个子问题的解。
- 方程： 用数学表达式来描述状态之间的转换关系。
状态转移方程的作用
- 刻画问题结构： 将复杂问题分解为一系列简单的子问题，并描述子问题之间的关系。
- 指导求解过程： 提供了从已知子问题解求解未知子问题解的递推关系。
- 优化算法效率： 通过避免重复计算子问题，提高算法效率。
状态转移方程的一般形式
1 | dp[i] = f(dp[i-1], dp[i-2], ..., dp[i-k], other_info) |
dp[i]：表示当前状态的解。f：表示状态转移函数，即根据前面的状态和其它信息计算当前状态的解。dp[i-1], dp[i-2], ..., dp[i-k]：表示前面的状态的解。other_info：表示其他影响状态转移的信息。
例子：0-1背包问题
- 问题描述： 有一个背包，容量为W，有n个物品，每个物品有重量w[i]和价值v[i]，如何选择物品放入背包，使得背包中物品的总价值最大？
- 状态定义： dp[i][j]表示前i个物品中选择，且总重量不超过j的情况下，能够获得的最大价值。
- 状态转移方程：
1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
dp[i-1][j]：不选择第i个物品的最大价值。dp[i-1][j-w[i]] + v[i]：选择第i个物品，那么背包容量减少w[i]，价值增加v[i]。
如何写出状态转移方程
- 明确问题： 理解问题的含义，确定问题的目标。
- 定义状态： 找到一个合适的量来表示子问题的解。
- 寻找状态转移： 分析问题，找出状态之间的关系，即如何从已知状态推导出未知状态。
- 写出方程： 根据状态转移关系，用数学表达式表示出来。
总结
状态转移方程是动态规划的核心，掌握了状态转移方程，就能解决很多动态规划问题。在实际应用中，状态转移方程的设计往往是解决问题的关键。
