动态规划与状态转移方程的基本概念
动态规划的核心思想是将复杂问题拆解为若干个相互关联的子问题，通过求解子问题的最优解，逐步推导出原问题的最优解。状态转移方程就是描述子问题之间关联关系的数学表达式，它定义了如何从已知状态推导出未知状态。
很多动态规划问题的子问题存在重叠性，比如计算斐波那契数列时，fib(5)的计算需要用到fib(4)和fib(3)，而fib(4)的计算又需要用到fib(3)和fib(2)，其中fib(3)会被重复计算多次。如果每次都重新计算这些子问题，会浪费大量计算资源，这时候就需要保存中间变量的计算结果。
用数组保存中间变量的核心思路
数组是一种连续存储的线性数据结构，支持通过下标快速访问元素，非常适合用来保存动态规划的中间计算结果。我们可以定义一个数组，数组的下标对应动态规划的状态，数组的值对应该状态下的最优解或者中间计算结果。
具体实现步骤如下：
- 首先确定动态规划的状态定义，明确每个状态代表的含义
- 根据问题逻辑推导状态转移方程，明确状态之间的推导关系
- 初始化数组，设置边界状态的值
- 按照状态转移方程的顺序，遍历计算各个状态的值，将结果存入数组对应下标的位置
- 最终从数组中获取原问题对应的状态值，即为问题的最优解
经典案例实现
案例一：斐波那契数列计算
斐波那契数列的定义是fib(0)=0，fib(1)=1，当n>=2时，fib(n)=fib(n-1)+fib(n-2)。我们用数组保存每个fib(n)的计算结果，避免重复计算。
public class Fibonacci {
public static int fib(int n) {
// 边界判断
if (n < 0) {
return -1;
}
if (n <= 1) {
return n;
}
// 定义数组保存中间结果，下标i对应fib(i)的值
int[] dp = new int[n + 1];
// 初始化边界状态
dp[0] = 0;
dp[1] = 1;
// 按照状态转移方程计算后续状态
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回最终结果
return dp[n];
}
public static void main(String[] args) {
System.out.println(fib(10)); // 输出55
}
}
案例二：0-1背包问题
0-1背包问题描述为：有N件物品和一个容量为W的背包，第i件物品的重量是weight[i]，价值是value[i]，每件物品只能选一次，求背包能装下的最大价值。我们用二维数组保存中间状态，dp[i][j]表示前i件物品放入容量为j的背包时的最大价值。
状态转移方程为：如果第i件物品重量大于j，那么dp[i][j] = dp[i-1][j]；否则dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])。
def zero_one_knapsack(weights, values, capacity):
n = len(weights)
# 定义二维数组保存中间状态，多一行一列方便处理边界
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# 遍历所有物品
for i in range(1, n + 1):
# 遍历所有容量
for j in range(1, capacity + 1):
# 当前物品重量大于背包容量，无法放入
if weights[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
# 选择放入或不放入，取最大值
dp[i][j] = max(dp[i-1][j], dp[i-1][j - weights[i-1]] + values[i-1])
# 返回最终最大价值
return dp[n][capacity]
# 测试数据：3件物品，重量分别为2、3、4，价值分别为3、4、5，背包容量5
weights = [2, 3, 4]
values = [3, 4, 5]
capacity = 5
print(zero_one_knapsack(weights, values, capacity)) # 输出7
优化思路与注意事项
在使用数组保存中间变量时，还可以根据问题特性做进一步优化。比如斐波那契数列的计算中，每个状态只依赖前两个状态，不需要保存整个数组，只需要用两个变量交替存储即可，这样可以把空间复杂度从O(n)降到O(1)。
另外需要注意数组的大小设置，要确保数组下标能够覆盖所有可能的状态，避免数组越界。同时状态转移的计算顺序要和状态之间的依赖关系一致，比如0-1背包问题中，二维数组的计算需要先遍历物品再遍历容量，并且容量要从大到小遍历，才能保证每个物品只被选择一次。
通过数组保存动态规划的中间计算结果，能够有效避免重复计算，大幅提升算法效率，是动态规划实现中最常用的方法之一，掌握这种思路可以帮助解决更多复杂的动态规划问题。