数据结构与算法 / 系统课时

一维动态规划

一维动态规划

一维动态规划适合状态只随一个主变量变化的问题。本课用“最大非相邻元素和”说明如何定义前缀状态、处理状态下标与数组下标的偏移,并在保证依赖正确的前提下完成线性转移。

学习目标

  • 使用“前 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]。因此:

text
dp[i] = max(
    dp[i - 1],
    dp[i - 2] + values[i - 1]
)

最大非相邻元素和的状态转移

状态只保留了未来所需的最优值,不必记录此前具体选择了哪些元素,因此满足无后效性。需要恢复选择方案时,再保留完整状态数组并从末尾反向判断来源。

主示例:构造一维状态数组

下面的 Java 17 程序允许负数输入且允许不选任何元素,因此全负数组的答案为 0。完整数组便于观察每一步从哪个状态转移而来。

java
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;
    }
}

预期输出:

text
状态数组: [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)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

一维动态规划

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通