编辑“︁状态转移方程”︁

= 状态转移方程 =

状态转移方程（State Transition Equation）是动态规划（Dynamic Programming, DP）中的核心概念，它定义了如何从一个或多个子问题的解推导出当前问题的解。理解状态转移方程是掌握动态规划的关键，因为它描述了问题的递推关系。

== 基本概念 ==

在动态规划中，我们通常将问题分解为若干子问题，并通过解决这些子问题来构建原问题的解。状态转移方程则描述了如何从已知的子问题解推导出当前问题的解。

数学上，状态转移方程可以表示为：
<math>
dp[i] = f(dp[j]), \quad j < i
</math>
其中，<math>dp[i]</math> 表示状态 <math>i</math> 的解，<math>f</math> 是某种递推函数，<math>j</math> 是比 <math>i</math> 更小的状态。

== 状态转移方程的设计步骤 ==
设计状态转移方程通常包括以下步骤：
1. '''定义状态'''：明确 <math>dp[i]</math> 表示什么。
2. '''确定初始条件'''：定义边界状态（如 <math>dp[0]</math> 或 <math>dp[1]</math>）。
3. '''推导递推关系'''：找到 <math>dp[i]</math> 与更小子问题之间的关系。
4. '''确定计算顺序'''：通常从初始状态开始，逐步计算到目标状态。

== 示例 1：斐波那契数列 ==
斐波那契数列是动态规划的经典示例。其状态转移方程为：
<math>
F(n) = F(n-1) + F(n-2), \quad F(0) = 0, \quad F(1) = 1
</math>

以下是 Python 实现：
<syntaxhighlight lang="python">
def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fibonacci(5))  # 输出：5
</syntaxhighlight>

=== 输入与输出 ===
输入：<code>n = 5</code><br>
输出：<code>5</code><br>
解释：斐波那契数列的第 5 项是 5（0, 1, 1, 2, 3, 5）。

== 示例 2：背包问题 ==
背包问题是动态规划的另一个经典问题。给定物品的重量 <math>w</math> 和价值 <math>v</math>，以及背包的容量 <math>W</math>，目标是最大化背包中物品的总价值。

状态转移方程为：
<math>
dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
</math>
其中：
* <math>dp[i][j]</math> 表示前 <math>i</math> 个物品放入容量为 <math>j</math> 的背包的最大价值。
* <math>w[i]</math> 和 <math>v[i]</math> 分别是第 <math>i</math> 个物品的重量和价值。

以下是 Python 实现：
<syntaxhighlight lang="python">
def knapsack(W, wt, val, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, W + 1):
            if wt[i-1] <= j:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - wt[i-1]] + val[i-1])
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][W]

wt = [2, 3, 4, 5]
val = [3, 4, 5, 6]
W = 5
n = len(wt)
print(knapsack(W, wt, val, n))  # 输出：7
</syntaxhighlight>

=== 输入与输出 ===
输入：<code>W = 5, wt = [2, 3, 4, 5], val = [3, 4, 5, 6], n = 4</code><br>
输出：<code>7</code><br>
解释：最优解是选择重量 2 和 3 的物品，总价值为 3 + 4 = 7。

== 实际应用场景 ==
状态转移方程广泛应用于：
* 路径规划（如最短路径问题）
* 资源分配（如任务调度）
* 字符串处理（如编辑距离）
* 游戏 AI（如博弈树搜索）

== 状态转移方程的优化 ==
在某些情况下，状态转移方程可以通过空间优化减少内存使用。例如，斐波那契数列问题可以仅用两个变量存储前两个状态：
<syntaxhighlight lang="python">
def fibonacci_optimized(n):
    if n == 0:
        return 0
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
</syntaxhighlight>

== 总结 ==
状态转移方程是动态规划的核心，它描述了如何从子问题的解推导出当前问题的解。通过合理定义状态和递推关系，可以高效解决许多复杂问题。初学者应从简单的例子（如斐波那契数列）入手，逐步掌握更复杂的问题（如背包问题）。

<mermaid>
graph TD
    A[定义状态 dp[i]] --> B[确定初始条件]
    B --> C[推导递推关系]
    C --> D[确定计算顺序]
    D --> E[得到最终解]
</mermaid>

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]