动态规划是一种通过把原问题分解为相对简单的子问题，并保存子问题解来避免重复计算，从而优化算法性能的方法，在JavaScript处理复杂计算场景时非常实用。它的核心思想是“记忆化”和“状态转移”，适合解决具有重叠子问题和最优子结构性质的问题。
动态规划的核心要素
要在JavaScript中实现动态规划，需要先明确三个核心要素：
- 状态定义：明确dp数组或dp变量的含义，即每个状态代表什么结果。
- 状态转移方程：找到当前状态和之前状态之间的推导关系，也就是如何从子问题的解得到原问题的解。
- 边界条件：确定最基础的子问题的解，避免递归或递推时出现越界或者无限循环。
实战案例一：爬楼梯问题
爬楼梯是动态规划入门的经典问题：假设你正在爬楼梯，需要n阶才能到达楼顶，每次你可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶？
首先分析状态：设dp[i]表示爬到第i阶台阶的方法数。那么第i阶可以从第i-1阶爬1步到达，也可以从第i-2阶爬2步到达，因此状态转移方程为dp[i] = dp[i-1] + dp[i-2]。边界条件是dp[1] = 1，dp[2] = 2。
以下是JavaScript的实现代码：
// 爬楼梯动态规划实现
function climbStairs(n) {
// 边界情况处理
if (n <= 2) return n;
// 定义dp数组，dp[i]表示爬到第i阶的方法数
const dp = new Array(n + 1);
// 初始化边界条件
dp[1] = 1;
dp[2] = 2;
// 递推计算dp数组
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 测试代码
console.log(climbStairs(3)); // 输出3
console.log(climbStairs(5)); // 输出8
这个实现的时间复杂度是O(n)，空间复杂度是O(n)，如果进一步优化的话，可以只用两个变量保存前两个状态，把空间复杂度降到O(1)。
实战案例二：最长递增子序列
最长递增子序列问题是：给定一个未排序的整数数组，找到最长递增子序列的长度。比如输入[10,9,2,5,3,7,101,18]，最长递增子序列是[2,3,7,101]，长度是4。
状态定义：dp[i]表示以第i个元素结尾的最长递增子序列的长度。对于每个i，我们需要遍历0到i-1的所有位置j，如果nums[j] < nums[i]，那么dp[i] = Math.max(dp[i], dp[j] + 1)。初始时每个dp[i]都是1，因为每个元素本身就是一个长度为1的子序列。
JavaScript实现代码如下：
// 最长递增子序列动态规划实现
function lengthOfLIS(nums) {
if (nums.length === 0) return 0;
// dp[i]表示以第i个元素结尾的最长递增子序列长度
const dp = new Array(nums.length).fill(1);
let maxLen = 1;
// 遍历每个元素
for (let i = 0; i < nums.length; i++) {
// 遍历i之前的所有元素
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
// 测试代码
const arr = [10,9,2,5,3,7,101,18];
console.log(lengthOfLIS(arr)); // 输出4
这个实现的时间复杂度是O(n²)，空间复杂度是O(n)，如果需要进一步优化时间复杂度，可以结合二分查找将时间复杂度降到O(n log n)。
动态规划的优化思路
在JavaScript中使用动态规划时，还可以从两个方向优化：
- 空间优化：如果dp数组的状态转移只依赖前几个状态，就可以用变量代替数组，减少空间占用，比如爬楼梯问题的空间优化版本。
- 状态压缩：对于二维dp数组，如果每次转移只用到上一行的状态，就可以压缩成一维数组，降低空间复杂度。
适用场景总结
动态规划适合解决以下几类JavaScript相关的算法问题：
- 计数类问题，比如爬楼梯、不同路径问题。
- 最值类问题，比如最长递增子序列、背包问题。
- 存在性问题，比如是否能拼出某个金额、是否能到达某个位置。
只要问题满足重叠子问题和最优子结构两个特性，就可以尝试用动态规划的思路来优化算法性能，避免暴力递归带来的时间浪费。
JavaScript动态规划算法优化dp数组修改时间：2026-06-20 11:57:18