带你读《图解算法小抄》二十一、动态规划（1）https://developer.aliyun.com/article/1347965?groupCode=tech_library
2.斐波那契数
1）题目描述
给定一个非负整数 n，计算 Fibonacci 数列中第 n 个数字的值。
Fibonacci 数列是一个递归定义的数列，其中每个数字是前两个数字之和。数列的前两个数字是 0 和 1，即 fib(0) = 0，fib(1) = 1。对于 n > 1 的情况，fib(n) = fib(n-1) + fib(n-2)。
例如，Fibonacci 数列的前几个数字是：0, 1, 1, 2, 3, 5, 8, 13, 21, ...
2）解题步骤
为了计算 Fibonacci 数列中第 n 个数字的值，我们可以使用动态规划的思想来优化计算过程。
- 定义状态：我们可以将 Fibonacci 数列的第 n 个数字作为状态。令 dp[i] 表示第 i 个数字的值。
- 初始状态：根据 Fibonacci 数列的定义，我们知道 dp[0] = 0，dp[1] = 1。
- 状态转移方程：根据 Fibonacci 数列的递推关系 dp[i] = dp[i-1] + dp[i-2]，我们可以使用状态转移方程来计算 Fibonacci 数列的其他数字。从 i = 2 开始，依次计算 dp[2] 到 dp[n] 的值。
- 边界条件：无需特别处理边界条件，因为初始状态已经包含了边界情况。
下面是使用动态规划解决 Fibonacci 数问题的算法框架：
function fibonacci(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]; }
3.打家劫舍
1）题目描述
给定一个非负整数数组 nums，表示每个房屋中的存放的金额。相邻的房屋在同一晚上会被抢劫，但是由于安全系统的限制，不能同时抢劫相邻的两个房屋。
请你计算在不触发警报的情况下，能够抢劫到的最大金额。
例如，给定一个包含以下金额的数组 nums：[2, 7, 9, 3, 1]，可以抢劫的最大金额为 12，即抢劫第 1 个房屋和第 3 个房屋。
2）解题步骤
为了计算在不触发警报的情况下能够抢劫到的最大金额，我们可以使用动态规划的思想来解决问题。
- 定义状态：我们可以将问题转化为每个房屋的最优解。令 dp[i] 表示抢劫到第 i个房屋时的最大金额。
- 初始状态：根据题目的约束，如果没有房屋可抢劫，即 nums 数组为空，那么最大金额为 0。即 dp[0] = 0。如果只有一个房屋，那么最大金额就是这个房屋里的金额。即 dp[1] = nums[0]。
- 状态转移方程：根据题目的要求，我们不能同时抢劫相邻的两个房屋。因此，对于第 i 个房屋，我们有两种选择：抢劫它或者不抢劫它。如果我们抢劫第 i 个房屋，那么最大金额为 dp[i-2] + nums[i-1]；如果我们不抢劫第 i 个房屋，那么最大金额为 dp[i-1]。因此，状态转移方程为 dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])。
- 最终解：问题的解即为最后一个房屋的最优解，即 dp[n]，其中 n 是房屋的数量。
下面是使用动态规划解决打家劫舍问题的算法框架：
function rob(nums) { const n = nums.length; if (n === 0) { return 0; } const dp = new Array(n + 1); dp[0] = 0; dp[1] = nums[0]; for (let i = 2; i <= n; i++) { dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]); } return dp[n]; }
带你读《图解算法小抄》二十一、动态规划（3）https://developer.aliyun.com/article/1347962?groupCode=tech_library
