动态规划通过记忆化避免重复计算，适用于最优子结构问题。文章以斐波那契数列、爬楼梯和最大子数组和为例，展示JS中DP的优化方法：从递归到记忆化，再到空间压缩；强调状态定义、转移方程与遍历顺序，利用变量复用实现时间O(n)、空间O(1)的高效解法，提升算法性能。
动态规划（Dynamic Programming，简称DP）是解决复杂问题的高效手段，尤其适用于具有重叠子问题和最优子结构的问题。在JavaScript中，合理使用动态规划不仅能提升算法效率，还能降低时间复杂度。本文通过实际案例，带你深入理解如何在JS中优化算法，实战应用动态规划。
理解动态规划的核心思想
动态规划的本质是“记住已经解决过的子问题”，避免重复计算。它通常用于求解最值问题，比如最长递增子序列、最小路径和、背包问题等。
关键步骤包括：
- 定义状态：明确dp数组或对象中每个元素代表的含义
- 状态转移方程：找出当前状态如何由之前的状态推导出来
- 初始化边界条件：处理最简单的情况
- 遍历顺序：确保在计算某个状态时，所需前置状态已计算完成
经典案例：斐波那契数列优化
斐波那契数列是最基础的动态规划入门题。原始递归写法存在大量重复计算，时间复杂度高达O(2^n)。
立即学习“Java免费学习笔记（深入）”；
使用记忆化递归或自底向上DP可将复杂度降至O(n)。
function fib(n, memo = {}) { if (n <= 1) return n; if (memo[n]) return memo[n]; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; }
进一步优化空间：只需保存前两个值。
function fib(n) { if (n <= 1) return n; let prev2 = 0, prev1 = 1; for (let i = 2; i <= n; i++) { const curr = prev1 + prev2; prev2 = prev1; prev1 = curr; } return prev1; }
空间复杂度从O(n)降到O(1)，适合大数值计算。
实战应用：爬楼梯问题（LeetCode 70）
每次可以爬1或2阶，问到第n阶有多少种走法。这本质上与斐波那契相同。
定义dp[i]为到达第i阶的方法数，状态转移方程为：
dp[i] = dp[i-1] + dp[i-2]
function climbStairs(n) { if (n <= 2) return n; let a = 1, b = 2; for (let i = 3; i <= n; i++) { const temp = a + b; a = b; b = temp; } return b; }
这个解法时间O(n)，空间O(1)，非常适合前端场景下的性能敏感操作。
进阶挑战：最大子数组和（LeetCode 53）
给定一个整数数组，找出连续子数组的最大和。
定义dp[i]表示以nums[i]结尾的最大子数组和。
状态转移：若dp[i-1] > 0，则将其加到当前数；否则从当前数重新开始。
function maxSubArray(nums) { let maxSum = nums[0]; let currentSum = nums[0];
for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); }
return maxSum; }
此方法无需额外数组存储，仅用两个变量维护状态，实现时间和空间双重优化。
基本上就这些。掌握状态定义和转移逻辑，结合JavaScript的语言特性（如灵活的对象和数组操作），能快速构建高效的动态规划解决方案。关键是多练典型题，形成思维模式。
