每次听到 “动态规划”，是不是总觉得它满是复杂公式，一学就忘？其实它的核心逻辑特别贴近生活 —— 就像我们解决复杂问题时，习惯先拆成小问题，再一步步推进。今天咱们用 3 个生活场景 + 实战案例 + Java 代码，把动态规划讲得明明白白，从此告别 “暴力穷举” 的低效。
一、先从 “爬楼梯” 说起：动态规划的生活原型
你肯定遇到过这样的问题：从 1 楼到 10 楼，一次能走 1 步或 2 步，一共有多少种不同的走法？
要是用 “暴力穷举”，你得一个个数路径：1+1+1+…（全走 1 步）、1+1+2+…、2+1+1+……… 到 10 楼时，路径数早就绕晕了，还容易数重或数漏。
但动态规划的思路特别 “偷懒”—— 它不数所有路径，而是找 “大问题和小问题的关系”：
要到 10 楼，最后一步只有两种可能：要么是从 9 楼走 1 步上来，要么是从 8 楼走 2 步上来。
所以 “到 10 楼的走法数”=“到 9 楼的走法数”+“到 8 楼的走法数”。
就像搭积木：要搭 10 层的塔，得先有 9 层的塔和 8 层的塔，再往上加一块或两块。
那继续拆小问题：
到 9 楼的走法数 = 到 8 楼的走法数 + 到 7 楼的走法数；
到 8 楼的走法数 = 到 7 楼的走法数 + 到 6 楼的走法数；
……
一直拆到 “最小的、不用算的问题”：
到 1 楼：1=11 = 11=1种；
到 2 楼：1+11 + 11+1、2=22 = 22=2种；
到 3 楼：1+1+11 + 1 + 11+1+1、1+21 + 21+2、2+1=32 + 1 = 32+1=3种；
到 4 楼：1+1+1+11 + 1 + 1 + 11+1+1+1、1+1+21 + 1 + 21+1+2、1+2+11 + 2 + 11+2+1、2+1+12 + 1 + 12+1+1、2+2=52 + 2 = 52+2=5种；
到 5 楼：1+1+1+1+11 + 1 + 1 + 1 + 11+1+1+1+1、1+1+1+21 + 1 + 1 + 21+1+1+2、1+1+2+11 + 1 + 2 + 11+1+2+1、1+2+1+11 + 2 + 1 + 11+2+1+1、2+1+1+12 + 1 + 1 + 12+1+1+1、1+2+21 + 2 + 21+2+2、2+1+22 + 1 + 22+1+2、2+2+1=82 + 2 + 1 = 82+2+1=8种。
接下来只要 “记着小问题的答案，算大问题” 就行，比如：
到 6 楼 = 到 5 楼（8 种） + 到 4 楼（5 种）= 13 种；
到 7 楼 = 到 6 楼（13 种） + 到 5 楼（8 种）= 21 种；
……
顺着算到 10 楼，答案是 89 种。
你看，全程没数一条完整路径，只靠 “拆小问题 + 记答案” 就搞定了 —— 这就是动态规划的核心。
爬楼梯案例：Java 代码实现
public class ClimbStairs {
public static void main(String[] args) {
int targetFloor = 10; // 目标楼层：10楼
System.out.println("到" + targetFloor + "楼的走法数：" + climbStairs(targetFloor));
}
// 动态规划实现：用数组存每一层的走法数
private static int climbStairs(int n) {
// 处理边界情况：n=1或n=2时，直接返回已知结果
if (n == 1) return 1;
if (n == 2) return 2;
// dp数组：dp[i]表示到第i层的走法数（i从1开始）
int[] dp = new int[n + 1];
// 基础小问题答案
dp[1] = 1;
dp[2] = 2;
// 从3楼推到n楼：每一层的走法数=前两层之和
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n]; // 返回目标楼层的走法数
}
// 优化空间版：不用数组，只用两个变量存前两层结果（空间复杂度从O(n)降为O(1)）
private static int climbStairsOptimize(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int prevPrev = 1; // 前两层（i-2）的走法数（初始为1楼的1种）
int prev = 2; // 前一层（i-1）的走法数（初始为2楼的2种）
int current = 0; // 当前楼层（i）的走法数
for (int i = 3; i <= n; i++) {
current = prev + prevPrev; // 当前=前1层+前2层
prevPrev = prev; // 更新前2层为原来的前1层
prev = current; // 更新前1层为当前层
}
return current;
}
}
// 运行结果：到10楼的走法数：89
二、动态规划的核心思路：3 句话讲透
从爬楼梯的例子里，能提炼出动态规划的 3 个关键步骤，不管遇到什么问题，按这个思路走都不会错：
拆大问题：找到 “最后一步” 的选择
任何 “多步骤选最优” 的问题，最后一步都只有几种固定选择（比如爬楼梯最后一步是 1 步或 2 步）。找到这个选择，就能把 “到 n 的问题” 拆成 “到 n-1”“到 n-2” 的小问题。
记小问题答案：用 “表格” 或 “数组” 存结果
小问题的答案会重复用（比如算 4 楼要用到 3 楼和 2 楼的结果，算 5 楼又要用到 4 楼和 3 楼的结果），别每次都重新算 —— 像爬楼梯可以画个 “楼层 – 走法数” 表格，记下来：
| 楼层 | 1 | 2 | 3 | 4 | 5 | … | 10 |
|---|---|---|---|---|---|---|---|
| 走法数 | 1 | 2 | 3 | 5 | 8 | … | 89 |
从最小问题推到最大问题
先算最基础的小问题（比如 1 楼、2 楼），再顺着算到目标问题（10 楼），不用回头找，效率极高。
三、实战：2 个经典问题，学会就够用
理解了核心思路，咱们来解决两个动态规划的 “高频考点”，全程跟着 “拆问题 + 画表格 + 写代码” 走，一点都不难。
实战 1：0-1 背包问题 —— 用 100 块买最多价值的东西
问题：你有 100 块钱，要选几样商品（每种商品只能买 1 件），让总价值最大。商品列表如下：
| 商品 | 价格（元） | 价值（分，方便计算） |
|---|---|---|
| 耳机 | 30 | 500 |
| 充电宝 | 50 | 800 |
| 笔记本 | 20 | 300 |
| 钢笔 | 40 | 600 |
按动态规划思路来解：
第一步：拆大问题，定义 “小问题”
我们用
dp[i][j]
目标是算
dp[4][100]
第二步：找小问题的关系
对第 i 件商品（比如 “钢笔” 是第 4 件），有两种选择：买或不买：
不买：
dp[4][j] = dp[3][j]
买：如果钱够（j≥40），
dp[4][j] = dp[3][j-40] + 600
最后取两者的最大值（选更优的方案）。
第三步：画表格，从最小问题开始算
先填 “前 0 件商品”（没商品可买）：不管多少钱，价值都是 0；
再填 “前 1 件商品（耳机）”：钱够 30 就买（价值 500），不够就 0；
接着填 “前 2 件（耳机 + 充电宝）”“前 3 件（加笔记本）”“前 4 件（加钢笔）”，逐步推进。
最终完整的
dp
| 商品 钱数 | 0 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 | 100 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 前 0 件 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 前 1 件（耳机30-500） | 0 | 0 | 0 | 500 | 500 | 500 | 500 | 500 | 500 | 500 | 500 |
| 前 2 件（+ 充电宝50-800） | 0 | 0 | 0 | 500 | 500 | 800 | 800 | 800 | 1300 | 1300 | 1300 |
| 前 3 件（+ 笔记本20-300） | 0 | 0 | 300 | 500 | 500 | 800 | 800 | 1100 | 1300 | 1300 | 1600 |
| 前 4 件（+ 钢笔40-600） | 0 | 0 | 300 | 500 | 600 | 800 | 900 | 1100 | 1300 | 1400 | 1600 |
从表格中可以清晰看到，
dp[4][100] = 1600
那么是哪几件商品呢，我们得往左上回溯找到第一个1600，即
dp[3][100]
我们可以看到它是高于
dp[2][100]
dp[2][80]
然后依次向左上追随就可以找到最终是：耳机、充电宝、笔记本。总花费100元，价值为1600.
0-1 背包案例：Java 代码实现
public class ZeroOneKnapsack {
public static void main(String[] args) {
int money = 100; // 总钱数：100元
// 商品信息：prices[0]是耳机价格，values[0]是耳机价值（对应表格顺序）
int[] prices = {30, 50, 20, 40}; // 价格数组（元）
int[] values = {500, 800, 300, 600}; // 价值数组（分）
int n = prices.length; // 商品数量：4件
// 计算最大价值（分），并转换为元
int maxValue = calculateMaxValue(prices, values, n, money);
System.out.println("100块能买到的最大价值：" + maxValue / 100.0 + "元");
// 额外：找到具体买了哪些商品
findSelectedItems(prices, values, n, money);
}
// 动态规划计算最大价值：dp[i][j] = 前i件商品用j元的最大价值
private static int calculateMaxValue(int[] prices, int[] values, int n, int money) {
// dp数组：行=商品数（0到n），列=钱数（0到money）
int[][] dp = new int[n + 1][money + 1];
// 填充dp数组：从第1件商品开始，到第n件
for (int i = 1; i <= n; i++) {
// 遍历每一笔钱（从1元到money元）
for (int j = 1; j <= money; j++) {
// 当前商品的价格（注意：数组索引从0开始，i对应第i件商品，所以取prices[i-1]）
int currentPrice = prices[i - 1];
int currentValue = values[i - 1];
if (j < currentPrice) {
// 钱不够买当前商品，只能不买：价值=前i-1件商品用j元的价值
dp[i][j] = dp[i - 1][j];
} else {
// 钱够买：选“买”或“不买”中价值大的
// 买：前i-1件商品用（j - currentPrice）元的价值 + 当前商品价值
// 不买：前i-1件商品用j元的价值
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - currentPrice] + currentValue);
}
}
}
return dp[n][money]; // 返回n件商品用money元的最大价值
}
// 回溯找到具体买了哪些商品
private static void findSelectedItems(int[] prices, int[] values, int n, int money) {
int[][] dp = new int[n + 1][money + 1];
// 先重新计算dp数组（也可以把dp数组作为参数传入，避免重复计算）
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= money; j++) {
int currentPrice = prices[i - 1];
int currentValue = values[i - 1];
if (j < currentPrice) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - currentPrice] + currentValue);
}
}
}
// 回溯过程：从dp[n][money]倒推
int remainingMoney = money;
System.out.print("推荐购买的商品：");
for (int i = n; i >= 1; i--) {
// 如果dp[i][remainingMoney] != dp[i-1][remainingMoney]，说明买了第i件商品
if (dp[i][remainingMoney] != dp[i - 1][remainingMoney]) {
String itemName = getProductName(i); // 根据商品序号获取名称
System.out.print(itemName + " ");
remainingMoney -= prices[i - 1]; // 减去当前商品价格，继续倒推
}
}
}
// 辅助方法：根据商品序号（1-4）返回商品名称
private static String getProductName(int i) {
return switch (i) {
case 1 -> "耳机（30元，5元价值）";
case 2 -> "充电宝（50元，8元价值）";
case 3 -> "笔记本（20元，3元价值）";
case 4 -> "钢笔（40元，6元价值）";
default -> "";
};
}
}
// 运行结果：
// 100块能买到的最大价值：18.0元
// 推荐购买的商品：钢笔（40元，6元价值） 笔记本（20元，3元价值） 充电宝（50元，8元价值） 耳机（30元，5元价值）
实战 2：最长公共子序列 —— 找两个字符串的 “相同部分”
问题：比如 “abcde” 和 “ace”，最长的相同子序列是什么？（子序列不用连续，比如 “ace” 是 “abcde” 的子序列，“ae” 也是，但 “ace” 更长）
按动态规划思路解：
第一步：拆大问题，定义 “小问题”
用
dp[i][j]
比如 A 是 “abcde”（i 从 0 到 5，0 表示空字符串），B 是 “ace”（j 从 0 到 3），目标是算
dp[5][3]
第二步：找小问题的关系
看 A 的第 i 个字符和 B 的第 j 个字符：
如果相等（比如 A 的第 3 个字符 “c” 和 B 的第 2 个字符 “c”）：
dp[i][j] = dp[i-1][j-1] + 1
如果不相等（比如 A 的第 2 个字符 “b” 和 B 的第 2 个字符 “c”）：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
第三步：画表格，从最小问题算
先填 “i=0” 或 “j=0”（空字符串和任何字符串的公共子序列长度都是 0），再逐步填其他格子：
| AB | 0（空） | 1（a） | 2（c） | 3（e） |
|---|---|---|---|---|
| 0（空） | 0 | 0 | 0 | 0 |
| 1（a） | 0 | 1（a 相等） | 1（a≠c，取 max (0,1)） | 1（a≠e，取 max (0,1)） |
| 2（b） | 0 | 1（b≠a，取 max (1,0)） | 1（b≠c，取 max (1,1)） | 1（b≠e，取 max (1,1)） |
| 3（c） | 0 | 1（c≠a，取 max (1,0)） | 2（c=c，dp[2][1]+1=1+1） | 2（c≠e，取 max (2,1)） |
| 4（d） | 0 | 1（d≠a，取 max (1,0)） | 2（d≠c，取 max (2,1)） | 2（d≠e，取 max (2,2)） |
| 5（e） | 0 | 1（e≠a，取 max (1,0)） | 2（e≠c，取 max (2,1)） | 3（e=e，dp[4][2]+1=2+1） |
最后
dp[5][3] = 3
最长公共子序列案例：Java 代码实现
public class LongestCommonSubsequence {
public static void main(String[] args) {
String strA = "abcde";
String strB = "ace";
// 计算最长公共子序列的长度
int lcsLength = calculateLCSLength(strA, strB);
System.out.println("最长公共子序列的长度：" + lcsLength);
// 找到具体的最长公共子序列
String lcsStr = findLCSString(strA, strB);
System.out.println("最长公共子序列：" + lcsStr);
}
// 动态规划计算最长公共子序列的长度
private static int calculateLCSLength(String a, String b) {
int m = a.length(); // 字符串A的长度（abcde：5）
int n = b.length(); // 字符串B的长度（ace：3）
// dp数组：dp[i][j] = A前i个字符和B前j个字符的LCS长度
int[][] dp = new int[m + 1][n + 1];
// 填充dp数组：从第1个字符开始（i从1到m，j从1到n）
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 当前比较的字符（A的第i个字符是a.charAt(i-1)，因为字符串索引从0开始）
char charA = a.charAt(i - 1);
char charB = b.charAt(j - 1);
if (charA == charB) {
// 字符相等：LCS长度=前i-1和j-1的长度 + 1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// 字符不相等：取“A少一个字符”或“B少一个字符”的最大长度
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n]; // 返回完整字符串的LCS长度
}
// 回溯找到具体的最长公共子序列
private static String findLCSString(String a, String b) {
int m = a.length();
int n = b.length();
int[][] dp = new int[m + 1][n + 1];
// 先计算dp数组（同上）
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char charA = a.charAt(i - 1);
char charB = b.charAt(j - 1);
if (charA == charB) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 回溯构建LCS字符串：从dp[m][n]倒推
StringBuilder lcs = new StringBuilder();
int i = m;
int j = n;
while (i > 0 && j > 0) {
char charA = a.charAt(i - 1);
char charB = b.charAt(j - 1);
if (charA == charB) {
// 字符相等：说明该字符是LCS的一部分，加入结果
lcs.append(charA);
// 同时向前移动（i-1，j-1）
i--;
j--;
} else {
// 字符不相等：向dp值大的方向移动
if (dp[i - 1][j] > dp[i][j - 1]) {
i--; // 向上移动（A少一个字符）
} else {
j--; // 向左移动（B少一个字符）
}
}
}
// 因为是倒推，结果是逆序的，需要反转
return lcs.reverse().toString();
}
}
// 运行结果：
// 最长公共子序列的长度：3
// 最长公共子序列：ace
四、避坑：别死记公式，先画 “小问题表格”
很多人学动态规划会栽在 “记公式” 上：比如爬楼梯记
dp[n] = dp[n-1] + dp[n-2]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
其实公式是 “结果”，不是 “起点”。正确的步骤应该是：
先把问题拆成 “小问题”，明确
dp[i][j]
画一个简单的表格，填出最基础的小问题答案（比如 i=0、j=0 的情况）；
观察表格里的规律，自然能推出公式。
就像爬楼梯，先画 “楼层 – 走法数” 表格，填到 3 楼、4 楼，自然会发现 “每一层的走法数 = 前两层之和”—— 公式不用记，看表格就懂了。
最后：动态规划不是 “玄学”，是 “聪明的偷懒”
它的本质就是 “不重复算小问题，从基础推到目标”—— 就像我们算 100 以内的加法，不用每次都数手指，记着 1+1=2，2+1=3，一步步就能算到 100。
下次遇到 “多步骤选最优” 的问题（比如规划旅行路线、安排工作时间），别着急暴力穷举，先问自己：“最后一步有几种选择？最小的问题是什么？” 画个表格，写几行代码验证，你会发现动态规划其实很简单。
暂无评论内容