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

动态规划适用条件

动态规划适用条件

动态规划不是“看到递归就建数组”,而是一套把重复状态只计算一次的方法。本课建立一套判断框架:先确认状态能否完整描述问题,再检查子问题是否重复、转移是否无环,以及局部最优能否组成整体最优。

学习目标

  • 判断一个问题是否具备可定义状态、重复子问题和有效状态转移。
  • 区分递归、记忆化搜索与自底向上动态规划。
  • 识别无后效性、最优子结构和状态设计中的常见陷阱。

判断框架

一个问题适合动态规划,通常需要同时回答四个问题。

  1. 能否用有限参数定义状态,例如 dp[i] 或 dp[i][j]?
  2. 当前状态能否由规模更小的状态转移得到?
  3. 不同求解路径是否会反复到达同一状态?
  4. 状态是否已经包含影响未来决策的全部信息?

对于最优化问题,还要检查最优子结构:整体最优解能否由子问题的最优解组合而成。若某个决策会依赖未记录的历史信息,就需要扩充状态,而不是直接套用原转移。

动态规划适用条件判断流程

三个关键条件

重复子问题

递归树中同一个参数组合被多次求值,才有缓存价值。若所有子问题都只出现一次,分治通常已经足够,额外的状态表反而增加空间和实现成本。

无后效性

一旦状态确定,未来结果不应再依赖状态之外的完整历史。例如路径问题若受“已经访问过哪些节点”影响,就必须把访问集合纳入状态,或改用其他算法。

最优子结构

对最优化问题,最优解中的子结构也应当是对应子问题的最优解。最长简单路径通常不具备容易利用的最优子结构,因为子路径选择会互相限制;最短路径在边权满足相应条件时则可以利用。

方法 是否缓存 计算顺序 适合场景
直接递归 否 按调用树展开 子问题不重复或规模很小
记忆化搜索 是 自顶向下,只访问需要的状态 状态稀疏、转移自然递归
自底向上 DP 是 按依赖顺序填表 状态密集、顺序明确、便于压缩空间

完整可运行示例

斐波那契数列不是最优化问题,但它能清楚展示“状态可定义、递推关系明确、子问题大量重复”这三个条件。下面的 Java 17 程序比较直接递归、记忆化搜索和自底向上计算的调用次数与结果。

java
import java.util.Arrays;

public class DynamicProgrammingConditionsDemo {

    private static long naiveCalls;
    private static long memoCalls;

    static long fibNaive(int n) {
        naiveCalls++;
        if (n <= 1) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    static long fibMemo(int n, long[] memo) {
        memoCalls++;
        if (n <= 1) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];
        }

        // 每个 n 的结果只计算一次,后续调用直接复用。
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    static long fibBottomUp(int n) {
        if (n <= 1) {
            return n;
        }

        long previous = 0;
        long current = 1;
        for (int i = 2; i <= n; i++) {
            // 当前状态只依赖前两个状态,因此可以把数组压缩为两个变量。
            long next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }

    public static void main(String[] args) {
        int n = 10;
        long naiveResult = fibNaive(n);

        long[] memo = new long[n + 1];
        Arrays.fill(memo, -1);
        long memoResult = fibMemo(n, memo);

        long bottomUpResult = fibBottomUp(n);

        System.out.println("n = " + n);
        System.out.println("直接递归: result = " + naiveResult + ", calls = " + naiveCalls);
        System.out.println("记忆化搜索: result = " + memoResult + ", calls = " + memoCalls);
        System.out.println("自底向上: result = " + bottomUpResult);
    }
}

运行命令:

bash
javac DynamicProgrammingConditionsDemo.java
java DynamicProgrammingConditionsDemo

预期输出

text
n = 10
直接递归: result = 55, calls = 177
记忆化搜索: result = 55, calls = 19
自底向上: result = 55

结果相同,但记忆化搜索避免了大量重复调用。自底向上版本进一步利用“只依赖前两个状态”的性质,把空间从 O(n)O(n) 压缩到 O(1)O(1)。

Tips、常见错误与练习

  • 先写出状态含义,再写转移方程。若一句话无法准确解释 dp[i][j] 表示什么,状态通常还没有设计清楚。
  • 有递推式不等于必须使用动态规划;没有重复子问题时,缓存不会降低渐进时间复杂度。
  • 转移依赖必须形成可计算顺序。若状态之间存在未处理的环,应重新定义状态、增加迭代收敛过程,或改用图算法。
  • 不要把贪心选择误认为最优子结构。贪心还要求局部最优选择可以安全地提前确定,条件比动态规划更强。

练习 1:统计爬楼梯问题中直接递归和记忆化搜索的调用次数。输入 n = 20,验收条件是两种方法结果一致,且记忆化调用次数随 n 线性增长。

练习 2:判断“区间内最大值查询”“0-1 背包”“归并排序”是否需要动态规划。对每个问题写出状态或子问题定义,并说明是否存在重复子问题,不能只给出是或否。

本课总结

  • 动态规划的核心是定义可复用状态,并按合法依赖关系只计算一次。
  • 重复子问题决定缓存是否有价值,无后效性决定状态是否完整。
  • 最优化问题还需满足最优子结构;条件不满足时应扩充状态或更换算法。

下一课预告

下一阶段将进入状态设计与转移方程,学习如何从业务约束中提取维度、初始化边界,并选择记忆化或自底向上的计算顺序。

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

目录与阅读设置

阅读设置

17

记录一个想法

动态规划适用条件

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

登录哪都通