带你读《图解算法小抄》二十一、动态规划（2）https://developer.aliyun.com/article/1347964?groupCode=tech_library
4.买卖股票的最佳时机
1）题目描述
给定一个数组 prices，它的第 i 个元素 prices[i] 表示某只股票在第 i 天的价格。你可以尽可能地完成更多的交易（多次买卖一支股票）。但是，你不能同时参与多笔交易（即，你必须在再次购买之前出售掉之前的股票）。
请你计算能够获得的最大利润。
2）解题步骤
为了计算能够获得的最大利润，我们可以使用动态规划的思想来解决问题。
- 定义状态：我们可以将问题转化为每一天的最优解。令 dp[i] 表示第 i 天的最大利润。
- 初始状态：根据题目的约束，如果只有一天的价格，那么最大利润为 0。即 dp[0] = 0。
- 状态转移方程：对于第 i 天，我们有两种选择：买入股票或卖出股票。如果我们决定买入股票，那么最大利润为 dp[i-1] - prices[i]；如果我们决定卖出股票，那么最大利润为 dp[i-1] + prices[i] - prices[i-1]。因此，状态转移方程为 dp[i] = max(dp[i-1] - prices[i], dp[i-1] + prices[i] - prices[i-1])。
- 最终解：问题的解即为最后一天的最优解，即 dp[n-1]，其中 n 是股票价格数组的长度。
下面是使用动态规划解决买卖股票的最佳时机问题的算法框架：
function maxProfit(prices) { const n = prices.length; if (n <= 1) { return 0; } const dp = new Array(n); dp[0] = 0; for (let i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] - prices[i - 1] + prices[i], dp[i - 1]); } return dp[n - 1]; }
5.最大子序和
1）题目描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
2）解题步骤
为了找到具有最大和的连续子数组，我们可以使用动态规划的思想来解决问题。定义状态：我们可以将问题转化为以每个元素结尾的连续子数组的最大和。令 dp[i] 表示以第 i 个元素结尾的连续子数组的最大和。
- 初始状态：根据题目的约束，以第一个元素结尾的连续子数组的最大和就是第一个元素本身。即 dp[0] = nums[0]。
- 状态转移方程：对于第 i 个元素，我们有两种选择：将其加入前一个子数组中或以当前元素为起点开始新的子数组。如果我们选择将其加入前一个子数组中，那么最大和为 dp[i-1] + nums[i]；如果我们选择以当前元素为起点开始新的子数组，那么最大和为 nums[i]。因此，状态转移方程为 dp[i] = max(dp[i-1] + nums[i], nums[i])。
- 最终解：问题的解即为所有连续子数组的最大和中的最大值，即 max(dp)。
下面是使用动态规划解决最大子序和问题的算法框架：
function maxSubArray(nums) { const n = nums.length; if (n === 0) { return 0; } const dp = new Array(n); dp[0] = nums[0]; let maxSum = dp[0]; for (let i = 1; i < n; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]); maxSum = Math.max(maxSum, dp[i]); } return maxSum; } }
带你读《图解算法小抄》二十一、动态规划（4）https://developer.aliyun.com/article/1347961?groupCode=tech_library
