前端算法之动态规划

• 动态规划
  • 动态规划解决什么问题
    • 最短路径问题：
    • 背包问题：
    • 最长公共子序列问题：
    • 最大子数组和问题：
    • 调度问题：
    • 编辑距离问题：
    • 矩阵链乘法问题：
  • 动态规划例子1
    • 下面是JavaScript实现代码：
  • 动态规划例子2 – 爬楼梯
  • 动态规划例子3 – 使用最小花费爬楼梯

动态规划

动态规划（Dynamic Programming）是一种算法思想，通常用于解决一些优化问题和最优解问题。

它的基本思路是 将一个大问题拆分成若干个小问题，先解决小问题，再合并得到原问题的解。

动态规划算法通常包括以下几个步骤：

1. 定义状态：将原问题拆分成若干个子问题，并将子问题中需要求解的参数定义为状态。

2. 状态转移方程：通过状态之间的转移得到更大规模的子问题的解，从而逐步推导出原问题的解。

3. 边界条件：确定最小的子问题，即边界条件。

4. 计算顺序：按照子问题的规模从小到大依次计算，确保每一个子问题的解都已经求出。

动态规划算法的时间复杂度通常为O(n^2)，与子问题的规模有关。

它在求解最优解问题、背包问题、最长公共子序列等问题中广泛应用。

动态规划解决什么问题

动态规划是一种解决优化问题的算法思想，它通过将问题分解为子问题，并利用子问题的解来构建原问题的解。

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。

动态规划可以解决很多问题，包括但不限于以下几类：

最短路径问题：

如在一个有向图中找到两个节点之间的最短路径。

背包问题：

如在给定容量的背包中选择一组物品使得价值最大化，同时要保持总重量不超过背包容量。

最长公共子序列问题：

如给定两个序列，找到它们最长的共同子序列。

最大子数组和问题：

如找到一个数组中连续子数组的最大和。

调度问题：

如在给定一组任务和资源的情况下，确定任务的最佳调度顺序以最小化完成时间或最大化资源利用率。

编辑距离问题：

如找到将一个字符串转换为另一个字符串所需的最少编辑操作次数（插入、删除、替换）。

矩阵链乘法问题：

如找到一组矩阵相乘的最佳顺序，使得总乘法次数最少。

以上只是动态规划能够解决的一部分问题，实际上动态规划广泛应用于许多领域，包括计算机科学、运筹学、经济学等。

通过合理设计状态转移方程和使用适当的技巧，可以有效地利用动态规划算法解决各种复杂的优化问题。

更多详细内容，请微信搜索“前端爱好者“， 戳我 查看 。

动态规划例子1

以下是使用JavaScript实现动态规划的一个例子，

假设有一个长度为n的数组A，需要从中选出一些数，使得它们的和最大，但是选出的数不能相邻。

这就是一个典型的最优解问题，可以使用动态规划算法来求解。

首先定义状态： 设f(i)为前i个数中选取不相邻数能够获得的最大和。那么问题的解就是f(n)。

状态转移方程： 对于前i个数，如果选第i个数，则不能选第i-1个数，所以其最大和为f(i-2)+A[i]；如果不选第i个数，则其最大和为f(i-1)，因此f(i)应该为这两者中的最大值。

边界条件： 对于前0个数，其最大和为0，即f(0)=0；对于前1个数，其最大和为A[0]，即f(1)=A[0]。

计算顺序： 按照子问题的规模从小到大依次计算，确保每一个子问题的解都已经求出。因此，可以使用循环从2开始逐步计算f(2)、f(3)、…、f(n)，最终得到f(n)即为问题的解。

下面是JavaScript实现代码：

function maxSum(A) {
    let n = A.length;
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return A[0];
    } else {
        let f = new Array(n + 1);
        f[0] = 0;
        f[1] = A[0];
        for (let i = 2; i <= n; i++) {
            f[i] = Math.max(f[i - 2] + A[i - 1], f[i - 1]);
        }
        return f[n];
    }
}

// 示例
let A = [1, 2, 4, 1, 7, 8, 3];
let result = maxSum(A);
console.log(result); // 输出15

以上代码中，我们定义了一个函数maxSum，该函数接受一个数组A作为参数，返回选取不相邻数能够获得的最大和。

在函数内部，我们首先判断输入数组的长度，如果长度为0，则直接返回0；如果长度为1，则返回数组的唯一元素。

对于长度大于1的数组，我们创建一个长度为n+1的数组f，其中f[i]表示前i个数中选取不相邻数能够获得的最大和。

接着，我们按照上述状态转移方程和边界条件，使用循环从2开始逐步计算f数组的每个元素，最终得到f[n]即为问题的解。

动态规划例子2 – 爬楼梯

leetcode地址：https://leetcode.cn/problems/climbing-stairs/description/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
    1. 1 阶 + 1 阶
    2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶

提示：

1 <= n <= 45

------------------------- 思路 -------------------------

1. 定义子问题
2. 根据要执行的问题，重复执行子问题
3. 找到边界

设跳上 n 级台阶有 f(n)种跳法。

在所有跳法中，青蛙的最后一步只有两种情况：

• 跳上 1 级

• 2 级台阶。

• 当为 1级台阶： 剩 n?1个台阶，此情况共有 dp(n?1)种跳法。

• 当为 2级台阶： 剩 n?2个台阶，此情况共有 dp(n?2)种跳法。

即 dp(n) 为以上两种情况之和，即 dp(n)=dp(n?1)+dp(n?2)，以上递推性质为斐波那契数列。

因此，本题可转化为 求斐波那契数列的第 nnn 项，区别仅在于初始值不同：

• 青蛙跳台阶问题： dp(0)=1 , dp(1)=1 , dp(2)=2 。
• 斐波那契数列问题： dp(0)=1 , dp(1)=1 , dp(2)=2 。

实现代码

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    // 1. 定义子问题
    // 2. 根据要执行的问题，重复执行子问题
    // 3. 找到边界

    // dp[0] = 1 一次爬一到两个台阶，一次爬一阶梯是一步
    // dp[1] = 1 爬第二节台阶也是一步
    let dp = [1,1] 

    // dp[i] = dp[i-1] + dp[i-2] -- dp[i]代表当前台阶位置，

    // 因为之前定义了第零阶梯和第一阶梯，所以，要从第二阶梯开始
    for(let i = 2; i <= n ;i ++){
       dp[i] = dp[i-1] + dp[i-2] // 子问题的标准：上一个点与下一个节点的关系
    } 

    return dp[n]
};

动态规划例子3 – 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。

一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
    - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
    总花费为 15 。

示例 2：

输入：cost = ['1',100,'1',1,'1',100,'1','1',100,'1']
输出：6
解释：你将从下标为 0 的台阶开始。
    - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
    - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
    - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
    - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

2 <= cost.length <= 1000
0 <= cost[i] <= 999

实现代码

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
    cost.push(0) // 不爬台阶，费用为0，也就是边界为0
    let dp = []
    let n = cost.length

    dp[0] = cost[0]
    dp[1] = cost[1]

    // 当前台阶费用，取决于上一级台阶费用【一次爬一个】或者上上节台阶费用【一次爬两个台阶】加上当前费用
    // dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i]
    for(let i = 2; i < n;i++){
        dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i]
    }

    return dp[n-1] 
};