JavaScript中什么是动态规划_JavaScript实现

动态规划是通用算法思想，核心为“用空间换时间”，需满足重叠子问题和最优子结构；JavaScript中可通过记忆化递归或迭代实现，如爬楼梯问题可用两变量优化求解。

动态规划（Dynamic Programming，简称 DP）不是 JavaScript 特有的概念，而是一种通用的算法设计思想；它在 JavaScript 中的实现方式与其他语言一致，核心是“用空间换时间”——通过保存子问题的解，避免重复计算，从而高效解决具有重叠子问题和最优子结构的问题。

动态规划的两个关键特征

重叠子问题：一个问题可以被分解为多个子问题，而这些子问题会反复出现。比如计算斐波那契数列第 n 项时，fib(n-1) 和 fib(n-2) 都会多次调用 fib(n-3)。

最优子结构：问题的最优解包含其子问题的最优解。例如爬楼梯最小花费、最长递增子序列、背包问题等，都可以由更小规模的同类问题推导得出。

JavaScript 中的两种常见实现方式

• 自顶向下（记忆化递归）：在递归基础上加一个缓存（如 Object 或 Map），每次计算前先查缓存，有则直接返回，无则计算后存入。

立即学习“Java免费学习笔记（深入）”；

• 自底向上（迭代 + 数组/变量）：从小规模子问题开始，用数组（或几个变量）按顺序推导出最终结果。更省内存，也更符合 JS 实际工程习惯。

多数简单 DP 问题（如斐波那契、爬楼梯）可用两个变量滚动更新，无需完整数组。

经典例子：爬楼梯（LeetCode 70）

假设你正在爬楼梯，每次可以跨 1 级或 2 级，问爬到第 n 级有多少种走法？

• 状态定义：dp[i] 表示到达第 i 级的方法数

标签： javascript java js ai