首页 > 文章 > 前端

动态编程变得简单：带有 JavaScript 示例的初学者指南

来源：dev.to

时间：2024-09-19 12:00:49 102浏览收藏

大家好，今天本人给大家带来文章《动态编程变得简单：带有 JavaScript 示例的初学者指南》，文中内容主要涉及到，如果你对文章方面的知识点感兴趣，那就请各位朋友继续看下去吧~希望能真正帮到你们，谢谢！

通过 javascript 中的动态编程释放高效解决问题的能力。

介绍

您想提高编程中解决问题的能力吗？ 动态规划（dp）是一种强大的技术，可以帮助您高效地解决复杂问题。本初学者指南将通过 javascript 示例向您介绍动态编程，使其易于掌握并应用于实际场景。

您将学到什么：

动态规划的基本概念
记忆和制表之间的差异
如何用 javascript 实现 dp 并结合实例
识别 dp 问题并应用正确策略的技巧

什么是动态规划？

动态规划是一种优化技术，用于通过将问题分解为更简单的子问题来解决问题。当问题涉及重叠子问题和最优子结构时，它特别有用。

关键概念

最优子结构：如果问题的最优解包含其子问题的最优解，则问题表现出最优子结构。
重叠子问题：问题可以分解为多次重复使用的子问题。

记忆与制表

动态编程可以通过两种方式实现：记忆（自上而下的方法）和制表（自下而上的方法）。

记忆（自上而下）

记忆化涉及存储昂贵的函数调用的结果，并在相同的输入再次发生时返回缓存的结果。

何时使用：

自然递归结构
需要避免冗余计算

javascript 示例：具有记忆功能的斐波那契数列

function fibmemo(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    memo[n] = fibmemo(n - 1, memo) + fibmemo(n - 2, memo);
    return memo[n];
}

// example usage:
console.log(fibmemo(10)); // output: 55

制表（自下而上）

制表通过从基本情况开始迭代地填充表格（数组）来解决问题。

何时使用：

首选迭代方法
所有子问题都需要至少解决一次

javascript 示例：带有制表的斐波那契数列

function fibtab(n) {
    if (n <= 1) return n;
    const fibtable = [0, 1];
    for (let i = 2; i <= n; i++) {
        fibtable[i] = fibtable[i - 1] + fibtable[i - 2];
    }
    return fibtable[n];
}

// example usage:
console.log(fibtab(10)); // output: 55

在 javascript 中实现动态编程

让我们探索如何应用动态编程来使用 javascript 解决实际问题。

1. 爬楼梯问题

问题陈述：

你正在爬一个有 n 级台阶的楼梯。您一次可以爬 1 或 2 级台阶。你可以通过多少种不同的方式登上顶峰？

具有记忆功能的动态编程解决方案：

function climbstairs(n, memo = {}) {
    if (n <= 2) return n;
    if (memo[n]) return memo[n];
    memo[n] = climbstairs(n - 1, memo) + climbstairs(n - 2, memo);
    return memo[n];
}

// example usage:
console.log(climbstairs(5)); // output: 8

说明：

问题有重叠的子问题（多次计算climbstairs(n - 1) 和climbstairs(n - 2)）。
记忆化存储这些结果，减少冗余计算。

2. 硬币找零问题

问题陈述：

给定一系列硬币面额和总金额，找到达到该金额所需的最少硬币数量。

带制表的动态规划解决方案：

function coinchange(coins, amount) {
    const dp = array(amount + 1).fill(infinity);
    dp[0] = 0;
    for (let coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] = math.min(dp[i], dp[i - coin] + 1);
        }
    }
    return dp[amount] === infinity ? -1 : dp[amount];
}

// example usage:
console.log(coinchange([1, 2, 5], 11)); // output: 3

说明：

我们建立一个表 dp，其中每个条目 dp[i] 代表数量 i 所需的最少硬币。
通过迭代更新dp，我们找到最优解。

认识动态规划问题

动态编程并不总是首选解决方案。以下是识别 dp 问题的方法：

最优子结构：问题能否分解为子问题，其解决方案会导致最优解？
重叠子问题：您是否多次解决同一个子问题？

常见 dp 问题类别：

斐波那契数列
爬楼梯
背包问题
最长公共子序列
矩阵链乘法

提示和最佳实践

从递归解决方案开始：在优化之前递归地理解问题。
清楚地定义状态：识别代表子问题状态的变量。
选择正确的方法：根据问题的性质在记忆和制表之间做出决定。
优化空间复杂性：尽可能通过仅存储必要的数据来减少空间使用。
使用小输入进行测试：使用小测试用例验证您的解决方案以确保正确性。

其他 javascript 示例

最长公共子序列 (lcs)

问题陈述：

给定两个字符串，找到它们的最长公共子序列的长度。

动态规划解决方案：

function lcs(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    return dp[m][n];
}

// Example Usage:
console.log(lcs("AGGTAB", "GXTXAYB")); // Output: 4