数据结构与算法 / 系统课时
一维动态规划
一维动态规划
一维动态规划适合状态只随一个主变量变化的问题。本课用“最大非相邻元素和”说明如何定义前缀状态、处理状态下标与数组下标的偏移,并在保证依赖正确的前提下完成线性转移。
学习目标
- 使用“前 i 个元素”定义一维前缀状态
- 从选择或跳过当前元素推导转移方程
- 处理空数组、负数输入和空间压缩顺序
前缀状态与下标映射
定义 dp[i] 为“前 i 个元素中,不选择相邻元素时能够得到的最大和”,并允许一个元素都不选。这样 dp[0] = 0 表示空前缀,dp[1] = max(0, values[0]) 表示只考虑数组下标 0 的元素。
状态下标 i 表示元素数量,不是原数组下标。计算 dp[i] 时,当前元素是 values[i - 1]。这种多留一个状态位置的设计能自然覆盖空输入,并减少特殊分支。
从两个选择得到转移
处理当前元素时只有两个互斥选择:跳过它,结果沿用 dp[i - 1];选择它,则前一个元素不能选,结果为 dp[i - 2] + values[i - 1]。因此:
dp[i] = max(
dp[i - 1],
dp[i - 2] + values[i - 1]
)
状态只保留了未来所需的最优值,不必记录此前具体选择了哪些元素,因此满足无后效性。需要恢复选择方案时,再保留完整状态数组并从末尾反向判断来源。
主示例:构造一维状态数组
下面的 Java 17 程序允许负数输入且允许不选任何元素,因此全负数组的答案为 0。完整数组便于观察每一步从哪个状态转移而来。
import java.util.Arrays;
public class OneDimensionalDpDemo {
public static void main(String[] args) {
int[] values = {2, 7, 9, 3, 1};
int[] dp = buildMaximumNonAdjacentSum(values);
System.out.println("状态数组: " + Arrays.toString(dp));
System.out.println("最大可选和: " + dp[values.length]);
}
private static int[] buildMaximumNonAdjacentSum(int[] values) {
if (values == null) {
throw new IllegalArgumentException("输入数组不能为 null");
}
int[] dp = new int[values.length + 1];
if (values.length == 0) {
return dp;
}
dp[1] = Math.max(0, values[0]);
for (int i = 2; i <= values.length; i++) {
int skipCurrent = dp[i - 1];
int chooseCurrent = dp[i - 2] + values[i - 1];
dp[i] = Math.max(skipCurrent, chooseCurrent);
}
return dp;
}
}预期输出:
状态数组: [0, 2, 7, 11, 11, 12]
最大可选和: 12最优值可由元素 2、9、1 组成,它们在原数组中互不相邻。状态数组只保证最优值,若要输出具体下标,需要根据 dp[i] 与 dp[i - 1] 的关系反向恢复。
空间压缩与常见错误
每一步只依赖前两个状态,因此可以用两个变量把空间从 O(n) 压缩到 O(1)。更新时必须先计算新状态,再把旧的 dp[i - 1] 和 dp[i - 2] 整体前移;过早覆盖会丢失下一轮仍需读取的值。
常见错误是使用 values[i],当 i == values.length 时会越界;选择当前元素时若从 dp[i - 1] 转移,则可能同时包含相邻元素。时间复杂度为 O(n),完整数组空间复杂度为 O(n),滚动变量空间复杂度为 O(1)。