动态规划（dynamic programing）的状态方程：python3实现_动态状态方程

《数据结构与算法分析——C语言描述 》P287 关于动态规划如下说到：
任何数学递归公式可以直接翻译成递归算法，但是基本现实是编译器常常不能正确对待递归算法，结果导致低效的算法。当我们怀疑很可能是这种情况时，我们必须给编译器一些帮助，将递归算法重新写成非递归算法，让后者把那些子问题的答案系统的记录在一个表内，利用这种方法的一种技巧叫做动态规划（dynamic programing）

用一个表代替递归：

• 现在我们以一个具体实例分析
  LeetCode 123. 买卖股票的最佳时机 III

• 每天都有3种状态：卖出；买进；休息：用 0 表示手里不持有股票；1表示持有股票
  然后再加入一个状态量k 表示 至今最多进行了k次交易。再用一个状态量i存储当前天数。

• 状态转移方程：
  dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
  解释如下：dp[i][k][0] :当前是第i+1天，至今最多进行了k次交易（可以没有进行交易，也可以是1次，k是使当前收益最大时的值。因为我们每次都做了选择）并且手上现在没有股票。这种状态的最大收益。

• 现在把k=2带入：
  dp[2][0] = max(dp[2][0], dp[2][1] + prices[i])
  dp[2][1] = max(dp[2][1], dp[1][0] - prices[i])
  dp[1][0] = max(dp[1][0], dp[1][1] + prices[i])
  dp[1][1] = max(dp[1][1], - prices[i]) # dp[0][0] = 0

• 初始条件 全部设为：dp[i][k][0] = 0 dp[i][k][1]= - infinite(因为没有股票时收益为0，在不能交易的时候有股票不可能）

• 终止条件：输出：dp[n-1][2][0]
  
  

• 优化空间后的代码如下：

def get_maxprofit2_optimize(prices):
    n = len(prices)
    dp = np.zeros((3,2))
    dp[2][0] = 0
    dp[1][0] = 0
    dp[1][1] = -float('inf')
    dp[2][1] = -float('inf')
    for i in range(n):
        dp[2][0] = max(dp[2][0], dp[2][1] + prices[i])
        dp[2][1] = max(dp[2][1], dp[1][0] - prices[i])
        dp[1][0] = max(dp[1][0], dp[1][1] + prices[i])
        dp[1][1] = max(dp[1][1], - prices[i])  # dp[0][0] = 0
    print(dp)
    return dp[2][0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

如果用DFS递归做，时间超时。

class Solution:
    def buy_sell(self, prices, head, tail):
        if prices[tail] - prices[head] >= 0:
            return prices[tail] - prices[head]
        else:
            return False

    def DFS(self, prices, head, sum2, ans, num):  # 在某一点开始搜索
        if num>=2:
            if sum2 >= ans:
                return sum2
            else:
                return ans
        for i in range(head, len(prices) - 1):  # 从i点购入股票
            for j in range(i + 1, len(prices)):  # 从j点卖出股票
                if self.buy_sell(prices, i, j):
                    sum2+=self.buy_sell(prices, i, j)
                    num+=1
                    ans = self.DFS(prices, j + 1, sum2, ans, num)
                    sum2-=self.buy_sell(prices, i, j) # 回溯的时候一定要还原回来，再往下搜索
                    num-=1 # 跟sum2同理
        if sum2 >= ans:
            return sum2
        else:
            return ans
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

参考资料