leetcode动态规划之买卖股票+打家劫舍

刷题的时候发现这两种可以单独放出来总结下。

121 买卖股票I

题目：给定一维数组代表每日的股票价格，只可以买入卖出一次，求最大利润
解析：股票系列的问题，一般定义的dp数组都是二维的，其中第二维只有0和1，0代表买入，1代表卖出，dp数组的含义也是和求的一样，递推公式直接看下面代码把

func maxProfit(prices []int) int {// 动态规划解法dp := make([][]int, len(prices))for i := 0; i < len(prices); i++ {dp[i] = make([]int, 2)}// 所以在这里初始化的是一个二维数组，且第二维度只有0和1两个值// 0代表持有该股票，1代表不持有该股票// 初始化DP数组dp[0][0] = -prices[0] // 若第一天就持有的话，只能是当天买入dp[0][1] = 0 // 若第一天不持有，很合理for i := 1; i < len(prices); i++ {dp[i][0] = max(dp[i-1][0], -prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])}return dp[len(prices)-1][1]
}func max(a, b int) int {if a > b {return a} return b
}

122 买卖股票II

题目：可多次买入和卖出

func maxProfit(prices []int) int {// 动态规划解法dp := make([][]int, len(prices))for i := 0; i < len(prices); i++ {dp[i] = make([]int, 2)}// 所以在这里初始化的是一个二维数组，且第二维度只有0和1两个值// 0代表持有该股票，1代表不持有该股票// 初始化DP数组dp[0][0] = -prices[0] // 若第一天就持有的话，只能是当天买入dp[0][1] = 0 // 若第一天不持有，很合理for i := 1; i < len(prices); i++ {dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) // 注意这一行dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])}return dp[len(prices)-1][1]
}func max(a, b int) int {if a > b {return a} return b
}

123 买卖股票III

题目：最多可完成两笔交易
解析：这道题需要细化五种dp状态：

没有操作
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

func maxProfit(prices []int) int {// 先定义DP数组dp := make([][]int, len(prices)) // 一维数组定义数量是输入数组的个数，二维的是5for i := 0; i < len(prices); i++ {dp[i] = make([]int, 5)}dp[0][0] = 0 // 初始化DP数组dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0for i := 1; i < len(prices); i++ {dp[i][0] = dp[i-1][0]dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])}return dp[len(prices)-1][4]
}
func max(a, b int) int {if a > b {return a}return b
}

188 买卖股票IIII

题目：可以完成K笔交易，k是入参
解析：k笔交易，每笔有买入和卖出两个操作，二维数组就是2k+1的大小，注意这道题初始化用取余操作，遍历的时候也用取余来判断到底是买入还是卖出
一共算下来是三个状态：

无状态
买入
卖出

func maxProfit(k int, prices []int) int {// k表示最多有k次交易dp := make([][]int, len(prices)+1)for i := 0; i < len(prices); i++ {dp[i] = make([]int, 2*k+1) // 每次交易表示买入和卖出,初始化二维数组里的每个数组}for i := 1; i < len(dp[0]); i++ { // 初始化的时候，对于第一天的所有可买入的case进行初始化if i % 2 != 0 {dp[0][i] = -prices[0]}}for i := 1; i < len(prices); i++ {dp[i][0] = dp[i-1][0]for j := 1; j < len(dp[0]); j++ {if j % 2 != 0 {dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])} else {dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])}}}return dp[len(prices) - 1][2*k] // 最后一天的最后一笔交易（初始化的时候是2*k+1）
}
func max(a, b int) int {if a > b {return a}return b
}

309 买卖股票有冷冻期

题目：卖出后冷冻期为1天
解析：这道题分为如下几种状态（记住下面的这些状态）：
状态0：处于买入状态
状态1：处于保持卖出状态
状态2：处于今天卖出状态
状态4：处于冷冻期

func maxProfit(prices []int) int {n := len(prices)dp := make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, 4) // 0123四种状态}dp[0][0] = -prices[0] // 只有第1天的买入情况需要初始化，其余的默认为0for i := 1; i < n; i++ { // 从第二天开始遍历dp[i][0] = max(dp[i-1][0], max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]))dp[i][1] = max(dp[i-1][1], dp[i-1][3])dp[i][2] = dp[i-1][0] + prices[i]dp[i][3] = dp[i-1][2]}return max(dp[n-1][1], max(dp[n-1][2], dp[n-1][3]))
}
func max(a, b int) int {if a > b {return a}return b
}

714 买卖股票加手续费

这个就很简单了，就是在买卖股票II上，卖出的时候减去手续费就行

func maxProfit(prices []int, fee int) int {n := len(prices)dp := make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, 2) // 0和11两种状态}dp[0][0] = -prices[0]for i := 1; i < n; i++ {dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)}return dp[n-1][1]
}
func max(a, b int) int {if a > b {return a}return b
}

198 打家劫舍

题目：给一个数组，不能连着偷，求最大的
解析：就正常的动态规划，定义好了初始值后就遍历

func rob(nums []int) int {if len(nums) == 1 { // 兼容测试用例return nums[0]}dp := make([]int, len(nums)+1)dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i := 2; i < len(nums); i++ {dp[i] = max(dp[i-1], dp[i-2] + nums[i])}return dp[len(nums)-1]
}func max(a, b int) int {if a > b {return a }return b
}

213 打家劫舍II

题目：需要偷的是一个环
解析：那就分成两个部分

0 – n-2
1 – n-1

然后再比较两个部分中的最大值

func rob(nums []int) int {if len(nums) == 1 {return nums[0]}if len(nums) == 2 {return max(nums[0], nums[1])}res1 := robRange(nums, 0, len(nums) - 2)res2 := robRange(nums, 1, len(nums) - 1)return max(res1, res2)
}func robRange(nums []int, start, end int) int {dp := make([]int, len(nums))dp[start] = nums[start]dp[start + 1] = max(nums[start], nums[start+1])for i := start + 2; i < len(nums); i++ {dp[i] = max(dp[i-1], dp[i-2] + nums[i])}return dp[end]
}
func max(a, b int) int {if a < b {return b}return a
}

337 打家劫舍III

题目：是一个二叉树，也不能连着偷
解析：其实用的是递归+二叉树的后续遍历，先求出左右子节点，在分别判断是偷合适还是不偷合适，用一个数组，0表示不偷，1表示偷

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rob(root *TreeNode) int {res := robTree(root)return max(res[0], res[1])
}func max(a, b int) int {if a > b {return a} return b
}func robTree(cur *TreeNode) []int{if cur == nil {return []int{0, 0}}// 二叉树后序遍历left := robTree(cur.Left)right := robTree(cur.Right)// 考虑去偷当前的屋子robCur := cur.Val + left[0] + right[0]// 考虑不偷当前的屋子notRobCur := max(left[0], left[1]) + max(right[0], right[1])return []int{notRobCur, robCur}
}