4. 动态规划入门：多阶段决策过程、状态转移方程、背包问题与调度问题的关联

动态规划，简称 DP。说实话，这名字起得挺唬人的。

我第一次接触 DP 是在大学算法课上，老师讲了一堆数学公式，我听得云里雾里。后来真正做调度系统了，才发现这东西其实就是一种「聪明的穷举法」。嗯，你没听错，就是穷举，只不过它知道怎么避免重复计算。

4.1 多阶段决策过程：把大问题拆成小问题

什么叫多阶段决策？说白了就是：一件事要分几步走，每一步你都得做个选择，而且后面的选择受前面选择的影响。

举个例子。我在做任务调度时，经常遇到这样的场景：

• 有 10 个任务要分配
• 每个任务可以分配给 3 个不同的机器
• 每个机器的处理能力不同
• 目标是让总完成时间最短

你想想看，如果暴力枚举所有分配方案，那是 3 的 10 次方种可能。机器一多，任务一多，直接爆炸。

但如果我们换个思路：

1. 先分配第 1 个任务，记录下每种分配后的状态
2. 再分配第 2 个任务，基于第 1 步的结果继续
3. 以此类推，直到所有任务分配完

这就是多阶段决策。每个阶段只关心「当前状态」和「当前选择」，不关心之前是怎么走到这一步的。

4.2 状态转移方程：DP 的灵魂

状态转移方程，说白了就是一个递推公式。它告诉你：当前状态 = f(上一个状态, 当前决策)

我个人习惯把状态转移方程写成这样：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight[i]] + value[i])

这个公式看着眼熟吧？没错，就是 0-1 背包问题的状态转移方程。

我来拆解一下：

• dp[i][j]：前 i 个物品，背包容量为 j 时的最大价值
• dp[i-1][j]：不选第 i 个物品
• dp[i-1][j - weight[i]] + value[i]：选第 i 个物品

为什么说它是灵魂？因为一旦你写对了状态转移方程，剩下的就是填表了。代码反而是最不重要的部分。

4.3 背包问题：调度问题的简化版

背包问题，其实是调度问题的一个特例。你想想看：

背包问题	调度问题
物品重量	任务耗时
物品价值	任务优先级/收益
背包容量	机器可用时间
选择物品	分配任务

我在做资源调度系统时，经常把任务分配问题建模成背包问题。比如：

// 0-1 背包问题代码示例
public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            if (j >= weights[i - 1]) {
                dp[i][j] = Math.max(dp[i - 1][j], 
                                    dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][capacity];
}

这段代码，说白了就是在填一张二维表。行是物品，列是容量，每个格子存的是当前最优解。

4.4 从背包到调度：状态定义的进化

背包问题的状态定义很简单：dp[i][j] 表示前 i 个物品，容量 j 时的最大价值。

但调度问题就复杂多了。比如多机调度：

• 状态可能是一个向量：每台机器的当前负载
• 决策可能是：把任务分配给哪台机器
• 目标可能是：最小化最大完成时间（makespan）

举个例子，两台机器的调度问题：

// 两台机器调度，最小化最大完成时间
// dp[i][j] 表示前 i 个任务，机器1负载为 j 时，机器2的最小负载
public int twoMachineScheduling(int[] tasks) {
    int n = tasks.length;
    int total = Arrays.stream(tasks).sum();
    int[][] dp = new int[n + 1][total + 1];
    
    // 初始化
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    dp[0][0] = 0;
    
    for (int i = 1; i <= n; i++) {
        int t = tasks[i - 1];
        for (int j = 0; j <= total; j++) {
            // 任务分配给机器1
            if (j >= t && dp[i - 1][j - t] != Integer.MAX_VALUE) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - t]);
            }
            // 任务分配给机器2
            if (dp[i - 1][j] != Integer.MAX_VALUE) {
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + t);
            }
        }
    }
    
    // 找最小最大完成时间
    int ans = Integer.MAX_VALUE;
    for (int j = 0; j <= total; j++) {
        if (dp[n][j] != Integer.MAX_VALUE) {
            ans = Math.min(ans, Math.max(j, dp[n][j]));
        }
    }
    return ans;
}

你看，状态定义从「一个数」变成了「一个数对」，复杂度也跟着上去了。但核心思想没变：多阶段决策 + 状态转移。

4.5 知识体系总览

下面这张图，是我自己总结的 DP 与调度问题的关联结构。画了好几个版本，这个最清晰：

4.6 实战中的 DP 思维

说了这么多理论，来点实际的。我在做调度系统时，遇到一个真实场景：

问题： 有 N 个任务，每个任务有截止时间和处理时长。一台机器，一次只能处理一个任务。如何安排顺序，让超时的任务最少？

这其实是一个带权重的调度问题。我的解法思路：

1. 先按截止时间排序（贪心思想）
2. 用 DP 记录「当前时间点能完成的最大任务数」
3. 状态转移：做 or 不做当前任务

// 任务调度：最小化超时任务数
// tasks[i] = {deadline, duration}
public int minOverdueTasks(int[][] tasks) {
    // 按截止时间排序
    Arrays.sort(tasks, (a, b) -> a[0] - b[0]);
    
    int n = tasks.length;
    int maxTime = tasks[n-1][0]; // 最大截止时间
    
    // dp[t] = 在时间 t 内能完成的最大任务数
    int[] dp = new int[maxTime + 1];
    
    for (int[] task : tasks) {
        int deadline = task[0];
        int duration = task[1];
        
        // 倒序遍历，避免重复使用同一个任务
        for (int t = deadline; t >= duration; t--) {
            dp[t] = Math.max(dp[t], dp[t - duration] + 1);
        }
    }
    
    // 最大可完成任务数
    int maxCompleted = 0;
    for (int t = 0; t <= maxTime; t++) {
        maxCompleted = Math.max(maxCompleted, dp[t]);
    }
    
    return n - maxCompleted; // 超时任务数
}

4.7 总结：DP 与调度的关系

最后，我想说几句掏心窝子的话。

动态规划不是万能的。它适合解决「有重叠子问题」和「最优子结构」的问题。调度问题恰好满足这两个条件，所以 DP 在调度领域应用广泛。

但要注意：

• 状态空间爆炸：任务一多，状态维度一高，DP 就扛不住了
• 这时候需要启发式算法、遗传算法等来救场
• DP 更多是作为「精确解」的基准，用来验证近似算法的效果

我在项目中，通常先用 DP 跑小规模数据，拿到最优解。然后拿这个最优解去调优启发式算法的参数。等参数调好了，再上大规模数据。这个流程，我建议你也试试。

---