2023-12-07
188. 买卖股票的最佳时机 IV （股票交易k次的通解）
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。提示：
1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
股票交易问题的特性：每个状态类型（如买入k次）都是由前一时刻的当前状态类型和上一状态类型（如买入k次、卖出k-1次+此次买入）求最大值转移得到的，存在固定的依赖关系。也就是说，最多交易k次的情况下，可能的状态一定是：操作0次、买入1次、（买入1次）卖出1次、买入2次、（买入2次）卖出2次……
根据这个特性，可以写出通解：
1func maxProfit(k int, prices []int) int { 2 n := len(prices) 3 if n <= 1 { 4 return 0 5 } 6 7 // dp数组存储动态规划中的状态信息 8 // dp[i][j] 表示在第i天，进行了j次操作时的最大利润 9 dp := make([][]int, n) 10 for i := range dp { 11 dp[i] = make([]int, 2*k+1) 12 } 13 14 // 初始化第一天的状态 15 for i := 0; i < n; i++ { 16 dp[i][0] = 0 17 } 18 19 // 初始化第一天买入的状态 20 for i := 1; i <= k; i++ { 21 dp[0][2*i-1] = -prices[0] 22 dp[0][2*i] = 0 23 } 24 25 // 动态规划过程 26 for i := 1; i < n; i++ { 27 for j := 1; j <= k; j++ { 28 // 更新买入状态 29 dp[i][2*j-1] = max(dp[i-1][2*j-1], dp[i-1][2*j-2]-prices[i]) 30 // 更新卖出状态 31 dp[i][2*j] = max(dp[i-1][2*j], dp[i-1][2*j-1]+prices[i]) 32 } 33 } 34 35 // 返回最后一天进行了k次交易时的最大利润 36 return dp[n-1][2*k] 37}
309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:输入: prices = [1]
输出: 0提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
1func maxProfit(prices []int) int { 2 n := len(prices) 3 // 如果数组长度小于等于1，无法完成交易，返回0 4 if n <= 1 { 5 return 0 6 } 7 8 // 创建一个二维数组 dp 用于存储状态转移信息 9 // dp[i][0]: 手上持有股票的最大收益 10 // dp[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益 11 // dp[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益 12 dp := make([][3]int, n) 13 14 // 初始化第一天的状态 15 dp[0][0] = -prices[0] 16 17 // 从第二天开始遍历股票价格数组 18 for i := 1; i < n; i++ { 19 // 更新持有股票状态的最大收益 20 dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) 21 22 // 更新冷冻期状态的最大收益 23 dp[i][1] = dp[i-1][0] + prices[i] 24 25 // 更新非冷冻期状态的最大收益 26 dp[i][2] = max(dp[i-1][1], dp[i-1][2]) 27 } 28 29 // 返回最后一天的最大收益，考虑非冷冻期的情况和冷冻期中的情况的较大值 30 return max(dp[n-1][1], dp[n-1][2]) 31}
55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。提示：
1 <= nums.length <= 104
0 <= nums[i] <= 105
1// 动态规划 2func canJump(nums []int) bool { 3 n := len(nums) 4 5 // 如果数组长度小于等于1，或者数组第一个元素为0，直接返回true 6 if n <= 1 || nums[0] == 0 { 7 return true 8 } 9 10 // dp数组用于记录每个位置的最大可达距离 11 dp := make([]int, n) 12 dp[0] = nums[0] 13 14 // 遍历数组，更新dp数组 15 for i := 1; i < n-1; i++ { 16 // 计算当前位置的最大可达距离 17 dp[i] = max(dp[i-1], i+nums[i]) 18 19 // 如果当前位置的最大可达距离已经能够到达或超过最后一个位置，返回true 20 if dp[i] >= n-1 { 21 return true 22 } 23 24 // 如果当前位置的最大可达距离小于等于当前位置，说明无法到达当前位置，返回false 25 if dp[i] <= i { 26 return false 27 } 28 } 29 30 // 遍历结束，返回true，因为能够到达最后一个位置 31 return true 32}