动态规划的基本实现框架

动态规划（Dynamic Programming, DP）是一种通过分解问题，将复杂的原问题转化为一系列简单的子问题，从而逐步求解得到最终解的算法技术。它的核心思想是将重叠的子问题的解进行存储和复用，从而避免重复计算，提高算法效率。今天我们将深入探讨动态规划的基本实现框架，并通过代码案例来帮助大家理解其具体实现方法。

1. 动态规划的五个步骤

动态规划的求解通常包括以下五个关键步骤，每一个步骤都至关重要。下面我们一一讲解：

1.1 定义状态（状态变量的选择）

在动态规划中，首先要明确如何定义状态，即如何表示子问题的解。状态变量用于存储子问题的解，并为后续的状态转移提供基础。

例子：背包问题
在背包问题中，我们希望将一定数量的物品放入背包中，要求总重量不超过背包容量，且总价值最大。我们可以定义一个状态 dp[i][w]，表示前 i 个物品中，背包容量为 w 时能够获得的最大价值。

1.2 定义状态转移方程（如何从子问题推导出原问题）

一旦确定了状态的定义，接下来就需要考虑如何从子问题推导出原问题的解。状态转移方程的核心思想是利用已经计算出的子问题的解来构建当前问题的解。

例子：背包问题
状态转移方程基于是否选择当前物品：

如果不选择当前物品：dp[i][w] = dp[i-1][w]
如果选择当前物品：dp[i][w] = dp[i-1][w - weight[i]] + value[i]

通过这种方式，我们可以根据当前问题的解，利用之前计算的子问题解来逐步构建整个问题的解。

1.3 初始化边界条件（边界情况下的值）

边界条件的初始化是非常重要的，因为它们通常对应于最小子问题的解。初始化时，边界条件代表了最小规模的子问题，它们为后续的计算提供了起点。

例子：背包问题
在背包问题中，当背包容量为 0 时，无论有多少物品，都无法放入任何物品，因此最大价值为 0。所以我们可以初始化 dp[0][w] = 0，对于所有的背包容量 w 都成立。

1.4 填充 DP 表格（自底向上的方式）

动态规划的核心是通过自底向上的方式填充 DP 表格。这个过程通常是迭代的，从最简单的子问题开始逐步解决，直到最终计算出原问题的解。

例子：背包问题
我们通过嵌套循环遍历每个物品和每个可能的背包容量，逐步填充 dp[i][w] 表格，直到最终计算出最大价值。

1.5 输出最终解（从表格中获取最终答案）

最终解通常会存储在 DP 表格的某个特定位置。我们从填充完的 DP 表格中提取最终答案。

例子：背包问题
在背包问题中，最终的最大价值通常存储在 dp[n][W] 中，其中 n 是物品的数量，W 是背包的容量。

2. 二维 DP 数组的使用

动态规划问题可以使用一维或二维的状态数组。在一些问题中，二维 DP 数组的使用非常常见，例如最长公共子序列（LCS）问题、最短路径问题等。

2.1 如何构建二维 DP 数组解决二维问题

对于二维 DP 问题，我们的目标是构建一个二维数组，并通过状态转移方程从子问题推导出当前问题的解。

例子：最长公共子序列（LCS）问题
假设我们有两个字符串 str1 和 str2，目标是求它们的最长公共子序列。可以定义一个二维 DP 数组 dp[i][j]，表示 str1[0..i-1] 和 str2[0..j-1] 的最长公共子序列的长度。状态转移方程如下：

如果 str1[i-1] == str2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1。
否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

通过逐步填充 dp 数组，最终得到 dp[m][n]，其中 m 和 n 分别是 str1 和 str2 的长度。

2.2 如何从状态转移方程构造 DP 数组

分析问题结构并建立状态转移方程后，我们可以构造 DP 数组。通常，对于二维数组，我们会使用两个嵌套循环，外循环遍历一个字符串的字符，内循环遍历另一个字符串的字符，并根据状态转移方程更新 dp[i][j]。

3. 状态压缩与空间优化

动态规划的空间复杂度通常与问题的规模成正比，但在许多情况下，可以通过状态压缩和空间优化减少空间的消耗。

3.1 状态压缩技术

许多动态规划问题的状态转移只依赖于当前状态和上一行的状态，因此可以将二维 DP 数组压缩为一维数组，显著减少空间复杂度。例如，在背包问题中，我们只需要保存当前物品的状态和前一个物品的状态，能够将二维数组压缩成一维数组。

例子：背包问题
原始的二维 DP 数组 dp[i][w] 可以通过使用一个一维数组 dp[w] 来代替，节省空间。

3.2 空间优化

动态规划的空间优化可以通过仅保留当前行和上一行的 DP 数组来节省内存。例如，在解决最长公共子序列问题时，我们可以通过只保留当前行和上一行的 DP 数组，来优化空间使用。

4. 动态规划算法的递推过程与表格填充

通过一个具体例子演示动态规划的递推过程和表格填充。考虑 斐波那契数列，要求计算第 n 个斐波那契数。

斐波那契数列的定义为：

F(0) = 0；
F(1) = 1；
F(n) = F(n-1) + F(n-2)，对于 n >= 2。

4.1 实现步骤

初始化 dp[0] = 0，dp[1] = 1。
使用状态转移方程 dp[i] = dp[i-1] + dp[i-2] 填充 DP 表格。
最终得到 dp[n]，这就是第 n 个斐波那契数。

4.2 代码实现

public class Fibonacci {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // 状态数组
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        // 填充 DP 表格
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
}