柚子快报邀请码778899分享：前端算法之动态规划
动态规划
动态规划解决什么问题
最短路径问题：背包问题：最长公共子序列问题：最大子数组和问题：调度问题：编辑距离问题：矩阵链乘法问题： 动态规划例子1
下面是JavaScript实现代码： 动态规划例子2 – 爬楼梯动态规划例子3 – 使用最小花费爬楼梯
动态规划
动态规划（Dynamic Programming）是一种算法思想，通常用于解决一些优化问题和最优解问题。
它的基本思路是 将一个大问题拆分成若干个小问题，先解决小问题，再合并得到原问题的解。
动态规划算法通常包括以下几个步骤：
定义状态：将原问题拆分成若干个子问题，并将子问题中需要求解的参数定义为状态。 状态转移方程：通过状态之间的转移得到更大规模的子问题的解，从而逐步推导出原问题的解。 边界条件：确定最小的子问题，即边界条件。 计算顺序：按照子问题的规模从小到大依次计算，确保每一个子问题的解都已经求出。
动态规划算法的时间复杂度通常为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]
};
柚子快报邀请码778899分享：前端算法之动态规划
参考阅读
发表评论