动态规划是解决重叠子问题的算法策略，背包问题因其阶段性决策、子问题重叠和最优子结构而适合DP；JavaScript中可用二维或空间优化的一维数组实现。
动态规划（Dynamic Programming，简称 DP）在 JavaScript 中不是某种内置语法，而是一种解题思想和算法策略：把大问题拆成重叠的子问题，用数组（或对象）“记下来”已算过的中间结果，避免重复计算，从而提升效率。
背包问题为什么适合用动态规划？
0-1 背包问题的经典描述是：给定 n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量为 W，每件物品最多选一次，求能装入的最大总价值。它的关键特征是：
- 决策具有阶段性（对每个物品，选或不选）
- 子问题重叠（比如“前 3 个物品、容量 5”这个状态会被多次用到）
- 最优解依赖于更小规模的最优解（无后效性）
这些正是动态规划适用的信号。
JavaScript 中实现 0-1 背包的二维 DP 解法
定义 dp[i][j] 表示考虑前 i 个物品、背包容量为 j 时能获得的最大价值。
立即学习“Java免费学习笔记（深入）”；
状态转移逻辑很直接：
- 如果不选第 i−1 个物品（索引从 0 开始）：dp[i][j] = dp[i−1][j]
- 如果选它（前提是 j ≥ w[i−1]）：dp[i][j] = dp[i−1][j − w[i−1]] + v[i−1]
- 取两者较大值
代码示例（简洁可运行）：
function knapsack(weights, values, W) {
const n = weights.length;
// 初始化二维数组，dp[i][j] 表示前 i 个物品、容量 j 的最大价值
const dp = Array(n + 1).fill().map(() => Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // 默认不选
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]
);
}
}
}
return dp[n][W];
}
// 示例调用
console.log(knapsack([2, 1, 3], [2, 8, 4], 4)); // 输出：10（选第 2 和第 3 个物品）
空间优化：一维数组就够了
观察发现，每次只依赖上一行，所以可用一维数组 dp[j] 滚动更新。但注意：内层循环要从右往左遍历容量，否则会重复使用刚更新的值（导致变成完全背包）。
function knapsackOptimized(weights, values, W) {
const dp = Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
// 从大到小遍历，防止覆盖未使用的旧状态
for (let j = W; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[W];
}
基本上就这些。动态规划的核心不在语法，而在建模——想清楚“状态是什么”“怎么转移”“边界在哪”。背包问题练熟了，再碰最长公共子序列、爬楼梯、编辑距离，思路就顺多了。
