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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

123 买卖股票III

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

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

func maxProfit(prices []int) int {
    // 先定义DP数组
    dp := make([][]int, len(prices)) // 一维数组定义数量是输入数组的个数，二维的是5
    for i := 0; i < len(prices); i++ {
        dp[i] = make([]int, 5)
    }
    dp[0][0] = 0 // 初始化DP数组
    dp[0][1] = -prices[0]
    dp[0][2] = 0
    dp[0][3] = -prices[0]
    dp[0][4] = 0
    for 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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天的买入情况需要初始化，其余的默认为0
    for 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36