动态规划通过记忆化避免重复计算，适用于重叠子问题与最优子结构，如斐波那契数列，朴素递归时间复杂度指数级，使用记忆化可降至O(n)。
面对复杂问题时，JavaScript中的算法优化往往决定程序的性能上限。动态规划与分治策略是两种高效解决递归类问题的核心方法，它们通过减少重复计算、合理拆解问题结构来显著提升执行效率。
动态规划：记忆化避免重复计算
动态规划适用于具有重叠子问题和最优子结构的问题。典型例子是斐波那契数列或背包问题。若使用朴素递归，时间复杂度会指数级增长。
以斐波那契为例：
朴素递归（低效）：function fib(n) {
if (n
return fib(n - 1) + fib(n - 2);
}
这个实现会重复计算大量相同子问题，比如 fib(5) 会多次调用 fib(2)。
立即学习“Java免费学习笔记（深入）”；
使用记忆化优化：
const memo = {};
function fib(n) {
if (n
if (memo[n]) return memo[n];
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
时间复杂度从 O(2^n) 降到 O(n)，空间换时间的经典体现。
自底向上的动态规划：进一步优化空间
在某些场景中，可以省去递归栈和哈希表存储，改用迭代方式从最小状态开始构建结果。
仍以斐波那契为例：
function fib(n) {
if (n
let a = 0, b = 1;
for (let i = 2; i
const temp = a + b;
a = b;
b = temp;
}
return b;
}
此时空间复杂度降为 O(1)，适合处理大规模数值问题。
分治策略：拆解问题，合并结果
分治法将大问题划分为独立子问题，分别求解后合并。常见应用包括归并排序、快速排序和二分查找。
以归并排序为例：
function mergeSort(arr) {
if (arr.length
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [], i = 0, j = 0;
while (i
if (left[i]
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
通过递归拆分数组，再有序合并，整体时间复杂度稳定在 O(n log n)。
动态规划 vs 分治：关键区别
两者都使用递归思想，但适用场景不同：
- 分治处理的是相互独立的子问题，如排序、搜索
- 动态规划针对子问题重叠的情况，强调状态存储与复用
- 分治通常不需要额外存储中间结果
- 动态规划常借助数组或对象缓存历史计算值
选择哪种策略，取决于问题是否具备重叠子结构。若子问题不重复，分治更合适；若存在大量重复计算，优先考虑动态规划。
基本上就这些，理解原理后，在实际编码中灵活运用，能大幅提升JavaScript程序的运行效率。
