动态规划学习笔记

一、动态规划概述

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解为子问题求解的算法思想。其核心特征是：当前阶段的状态由上一阶段状态和决策决定。

核心要素

动态规划解题步骤

1. 确认 dp 数组表示什么 — 明确 dp[i] 或 dp[i][j] 的含义
2. 写出状态转移方程 — 找出状态之间的递推关系
3. 确定初始值 — 给边界条件赋值
4. 确定遍历顺序 — 决定是从前往后还是从后往前

二、爬楼梯问题

问题描述

假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶。问有多少种不同的方法可以爬到楼顶？

状态定义

dp[n] 表示爬到第 n 阶台阶的方法数。

状态转移方程

dp[n] = dp[n-1] + dp[n-2]

爬到第 n 阶可以从第 n-1 阶爬 1 步上来，也可以从第 n-2 阶爬 2 步上来。

初始值

• dp[1] = 1
• dp[2] = 2

三种解法

解法一：递归（暴力法）

直接按照状态转移方程递归实现，存在大量重复计算，时间复杂度为 O(2ⁿ)。

解法二：动态规划（数组法）

使用 dp 数组存储中间结果，避免重复计算，时间复杂度为 O(n)，空间复杂度为 O(n)。

package cn.wolfcode.demo.servlet;

public class PaLouTi {
    public static int pa2(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

解法三：动态规划（空间优化法）

由于 dp[n] 只依赖 dp[n-1] 和 dp[n-2]，可以用两个变量代替整个数组，空间复杂度降为 O(1)。

package cn.wolfcode.demo.servlet;

public class PaLouTi {
    public static int pa3(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            int x = 1;  // dp[1]
            int y = 2;  // dp[2]
            int z = 0;  // dp[n]
            for (int i = 3; i <= n; i++) {
                z = x + y;
                x = y;
                y = z;
            }
            return z;
        }
    }
}

爬楼梯解法对比

三、01背包问题

问题描述

有一个容量为 V 的背包，还有 n 个物体。每个物体都有两个属性：重量 w 和价值 val。每个物体只有一件，问如何选择装入背包的物品，使得背包中物品的总价值最大？

示例数据

背包容量 V = 4

状态定义

dp[i][j] 表示有 i 个物品可选，放入容量为 j 的背包，产生的最大价值。

状态转移方程

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + val[i])

• dp[i-1][j]：不放入第 i 个物品，最大价值等于前 i-1 个物品在容量 j 下的最大价值
• dp[i-1][j-w[i]] + val[i]：放入第 i 个物品，最大价值等于前 i-1 个物品在剩余容量 j-w[i] 下的最大价值加上第 i 个物品的价值
• 取两者中的较大值

解题步骤

1. 确认 dp 数组：dp[i][j] 表示前 i 个物品放入容量 j 的背包的最大价值
2. 写状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + val[i])
3. 写代码：按行优先顺序填充 dp 表

01背包特点

• 每个物品只有一件，要么选要么不选
• 状态转移时只考虑"选"与"不选"两种决策
• 物品个数 n 和背包容量 V 决定了 dp 表的大小为 (n+1) × (V+1)

四、完全背包问题

问题描述

与 01 背包类似，但每个物品有无限件，即物品个数不限制。问如何选择装入背包的物品，使得背包中物品的总价值最大？

状态定义

dp[i][j] 表示有 i 个物品可选（每种物品无限件），放入容量为 j 的背包，最大价值。

状态转移方程

dp[i][j] = max(dp[i-1][j], dp[i][j - k*w[i]] + k * val[i])

• dp[i-1][j]：不放入第 i 个物品
• dp[i][j - k*w[i]] + k * val[i]：放入 k 件第 i 个物品（k 从 0 开始尝试）
• 注意这里用的是 dp[i] 而不是 dp[i-1]，因为第 i 个物品可以重复选

Java 实现

package cn.wolfcode.demo.servlet;

public class CompleteBackpack {
    // N 物品个数 V背包容量
    int N, V;
    // 重量
    private int[] w;
    // 价值
    private int[] val;
    // dp
    private int[][] dp;

    public void completeBackpack() {
        // 数组初始化 省略
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= V; j++) {
                for (int k = 0; k <= V / w[i - 1]; k++) {
                    if (j >= k * w[i - 1]) {
                        dp[i][j] = Math.max(
                            dp[i - 1][j - k * w[i - 1]] + k * val[i - 1],
                            dp[i][j]
                        );
                    } else {
                        dp[i][j] = dp[i][j];
                    }
                }
            }
        }
    }
}

完全背包特点

• 每个物品有无限件，可以重复选择
• 状态转移时需要遍历 k（选择该物品的件数）
• 与 01 背包的关键区别：dp[i][j] 的转移来源是 dp[i] 而非 dp[i-1]

五、01背包与完全背包对比

六、动态规划核心技巧总结

七、常见动态规划问题速查