详解动态规划

关于贪心算法的详解，请参考详解贪心算法

references:

看一遍就理解：动态规划详解

What is the role of recursion in Dynamic Programming?

动态规划的特点

对于使用动态规划解决的问题有如下几种特点：

• 可以分解成更小的问题来解决
• 拥有最佳子结构，也就是说求最佳 F(n)，通常依赖最佳 F(n-1)
• 通常是先解决子问题，最终选择出来最好的结果

动态规划解题步骤

• 通过穷举找到规律
• 确认边界
• 写状态转移方程和最优子结构
• 判断是否需要暂存结果

关于动态规划的思考: 递归 vs dp

关于递归

递归是函数中出现调用本身的代码，它解决的问题模型是：大的问题通过递归到小的问题最后递归到边界问题来解决。（很像 dp 解决的问题是吧）

summary

但 dp 实则是递归的升级，它通过总结递归过程中重复计算的那些点，对结果进行缓存，最终求得最佳答案。

在一些博客中讲 dp 有两种实现方式：（个人主要认为动态规划主要是自底向上的解决方法，但此处都列出来方便大家理解）

1. Bottom Up 自底向上

recursion 在这个过程中发挥的作用是辅助你理解！你可以通过穷举发现有哪些步骤被重复了，然后通过从最小的子问题开始解决+缓存结果来解决问题。

• 通常如果状态转移方程中决定答案的只有一个参数：F(n)= min(F(n-1),x) 此时一般通过单层循环+一维数组解决问题
• 如果状态转移方程中决定答案的有两个参数 F(n,arr)=min(F(n-1,arr[:i])) 此时一般通过双层循环+二维数组来解决问题

2. Top Down 自顶向下

这个过程通常通过 recursion 来解决问题，通常我们遇到一个问题时可以用递归写出来那么就该想想是不是能用动态规划来对递归进行优化即看子问题是否有重叠或重复计算的地方。

基于 dp 的经典算法

Kadane algorithm

kadane algorithm实质上是一种动态规划算法，

• 状态转移方程：F(n)=f(n)+F(n-1)>0?F(n-1):0;
• 最优子结构：F(n-1) 显然就是前面 n-1 个序列的子序列最大和，
• 但同时我们需要暂存 F(n) 的最大值

时间复杂度：O(n)

空间复杂度: O(1)

# kadane 伪代码
cur, res = 0, -sys.maxsize-1
for x in nums:
    # 负数是一个关键停止点
	cur = x + max(cur, 0)
	# res 实际上是在暂存 cur
	res = max(res, cur)
1
2
3
4
5
6
7

根据 kadane 算法你能写出来最小子数组和吗？

# 伪代码
cur, res = 0, sys.maxsize
for x in nums:
    # 正数是一个关键停止点
	cur = x + min(cur, 0)
	# res 实际上是在暂存 cur
	res = min(res, cur)
1
2
3
4
5
6
7

基于 kadane 算法的题目：

题解请参考我的 github repo

• 最大子数组和
• 环形子数组的最大和

例题

322. 零钱兑换

股票问题

传统的股票问题我们通常使用贪心算法即选定一个贪心策略然后计算就行了，LeetCode 上也有一些股票问题的变体，它们恰恰使用动态规划更合适

买卖股票的最佳时机 III-leetcode-123

class Solution:
    # 根据题解，我们知道一天结束后有如下几种状态
    # 未进行过任何操作；最大利润为 0
    # 只进行过一次买操作；代号 buy1 = max(buy1, -prices[i])
    # 进行了一次买操作和一次卖操作，即完成了一笔交易；sell1=max(sell1, buy1+prices[i])
    # 在完成了一笔交易的前提下，进行了第二次买操作；buy2 =max(buy2, sell1-prices[i])
    # 完成了全部两笔交易。sell2 = max(sell2, buy2+prices[i])
    # 和带冷冻状态的股票交易一样的思路，都是列出多个状态进行转移，很有意思
    # 时间复杂度：O(n)
    # 空间复杂度：O(1)
    def maxProfit(self, prices: List[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0
        for i in range(1, len(prices)):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        return sell2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最佳买卖股票时机含冷冻期-leetcode-309

class Solution:
    # 参考题解
    # f(i) 标识第 i 天我们的最大收益，它分为如下三种情况
    # f(i)(0) 当前持有一支股票
    # f(i)(1) 不持有股票，且处于冷冻期
    # f(i)(2) 不持有股票，不处于冷冻期
    # 对应的状态转移方程如下：
    # f[i][0] = max(f[i-1][2]-prices[i], f[i-1][0])
    # f[i][1] = f[i-1][0]+prices[i] 即卖出了
    # f[i][2] = max(f[i-1][2], f[i-1][1])
    # 边界条件 f(0) = 0
    def maxProfit0(self, prices: List[int]) -> int:
        length = len(prices)
        f = [[0, 0, 0] for i in range(length)]
        f[0][0] = -prices[0]
        for i in range(1, length):
            f[i][0] = max(f[i - 1][2] - prices[i], f[i - 1][0])
            f[i][1] = f[i - 1][0] + prices[i]
            f[i][2] = max(f[i - 1][2], f[i - 1][1])
        return max(f[length - 1][0], f[length - 1][1], f[length - 1][2])

    # 优化空间，最终时间复杂度 O(n)
    # 空间复杂度 O(1)
    def maxProfit(self, prices: List[int]) -> int:
        length, tmp0, tmp1, tmp2 = len(prices), -prices[0], 0, 0
        for i in range(1, length):
            tmp0_0, tmp1_1, tmp2_2 = tmp0, tmp1, tmp2
            tmp0 = max(tmp2_2 - prices[i], tmp0_0)
            tmp1 = tmp0_0 + prices[i]
            tmp2 = max(tmp2_2, tmp1_1)
        return max(tmp0, tmp1, tmp2)
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