当前位置：首页 > news >正文

动态规划 (Dynamic Programming) 算法概念-JS示例

news 2025/7/28 16:34:45

核心概念解析

动态规划是一种用于解决具有重叠子问题和最优子结构特性的复杂问题的算法设计技术。它通过将复杂问题分解为更小的子问题，并存储子问题的解来避免重复计算，从而提高效率。

关键特性

最优子结构：问题的最优解包含子问题的最优解
重叠子问题：在递归求解过程中，相同的子问题被多次计算
无后效性：某个阶段的状态一旦确定，就不会受到后续决策的影响

动态规划与分治法的区别

分治法：子问题不重叠，各自独立求解
动态规划：子问题重叠，通过存储中间结果避免重复计算

JavaScript 实例详解

1. 斐波那契数列

// 传统递归方法 - 效率低下 O(2^n)
function fibonacciRecursive(n) {if (n <= 1) return n;return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}// 动态规划方法 - 时间复杂度 O(n)，空间复杂度 O(n)
function fibonacciDP(n) {if (n <= 1) return n;// 创建状态数组const dp = new Array(n + 1);dp[0] = 0;dp[1] = 1;// 状态转移for (let i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}// 空间优化版本 - 空间复杂度 O(1)
function fibonacciOptimized(n) {if (n <= 1) return n;let prev2 = 0, prev1 = 1;for (let i = 2; i <= n; i++) {let current = prev1 + prev2;prev2 = prev1;prev1 = current;}return prev1;
}

2. 硬币找零问题

// 找到组成金额所需的最少硬币数
function coinChange(coins, amount) {// dp[i] 表示组成金额 i 所需的最少硬币数const dp = new Array(amount + 1).fill(Infinity);dp[0] = 0; // 组成金额0需要0个硬币// 对于每个金额for (let i = 1; i <= amount; i++) {// 尝试每种硬币for (let coin of coins) {if (coin <= i) {// 状态转移方程dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}return dp[amount] === Infinity ? -1 : dp[amount];
}// 示例使用
console.log(coinChange([1, 3, 4], 6)); // 输出: 2 (3+3)

3. 编辑距离问题

// 计算两个字符串之间的最小编辑距离
function minDistance(word1, word2) {const m = word1.length;const n = word2.length;// dp[i][j] 表示 word1[0...i-1] 转换为 word2[0...j-1] 的最小操作数const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));// 初始化边界条件for (let i = 0; i <= m; i++) dp[i][0] = i;for (let j = 0; j <= n; j++) dp[0][j] = j;// 状态转移for (let i = 1; i <= m; i++) {for (let j = 1; j <= n; j++) {if (word1[i - 1] === word2[j - 1]) {// 字符相同，无需操作dp[i][j] = dp[i - 1][j - 1];} else {// 取三种操作的最小值dp[i][j] = Math.min(dp[i - 1][j] + 1,     // 删除dp[i][j - 1] + 1,     // 插入dp[i - 1][j - 1] + 1  // 替换);}}}return dp[m][n];
}

4. 最长递增子序列

// 找到数组中最长递增子序列的长度
function lengthOfLIS(nums) {if (nums.length === 0) return 0;// dp[i] 表示以 nums[i] 结尾的最长递增子序列长度const dp = new Array(nums.length).fill(1);for (let i = 1; i < nums.length; i++) {for (let j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}return Math.max(...dp);
}// 优化版本 - 使用二分查找 O(n log n)
function lengthOfLISOptimized(nums) {const tails = [];for (let num of nums) {let left = 0, right = tails.length;// 二分查找插入位置while (left < right) {const mid = Math.floor((left + right) / 2);if (tails[mid] < num) {left = mid + 1;} else {right = mid;}}tails[left] = num;}return tails.length;
}

实际应用场景

1. 计算机科学领域

算法优化：在递归算法中避免重复计算
字符串处理：文本编辑器的差异比较、拼写检查
图形处理：图像压缩、模式识别
编译器设计：语法分析、代码优化

2. 业务应用

资源分配：项目管理中的任务调度
金融领域：投资组合优化、风险评估
电商推荐：个性化推荐系统
物流运输：路径规划、库存管理

3. 生物信息学

DNA序列比对：基因序列相似性分析
蛋白质结构预测：生物分子结构分析

4. 游戏开发

AI决策：游戏中的路径寻找
关卡设计：难度平衡计算

动态规划解题模板

function dynamicProgrammingSolution(problem) {// 1. 定义状态// dp[i] 或 dp[i][j] 表示什么含义// 2. 初始化边界条件// dp[0] = ..., dp[1] = ...// 3. 状态转移方程// for (let i = ...) {//     dp[i] = someFunction(dp[i-1], dp[i-2], ...)// }// 4. 返回结果// return dp[n] 或其他形式
}