动态规划和滚动数组的使用

vlambda
2020-01-18

动态规划和滚动数组的使用

题目大致意思是这样的：给你一个序列的股票价格，你要在合理的时候买入，合理的时候卖出，使其收益最大。

这里如果是直接暴力解决的话，从第k天买入，则卖出有n-k天可以选择，最终时间复杂度为O(n^2)。如果天数量级上去了，就有点难以接受了。

我这里使用动态规划来做，假设dp[i]表示第i天卖出能得到的最高收益，那么如果第i天不卖，选择在第i+1天卖出，而买入时间不变，能够得到的收益为：p[i+1]-dp[i]+dp[i]。但是这有可能会是一个负值，如果是负值而且在第i+1天卖出，我们可以选择不在之前时间买入，而选择在第i+1天买入再卖出，这样的收益为0.我们需要最大化这个收益，故最大收益为这个过程中的计算的所有结果里面最大的。

代码如下：

import numpy as np
p = [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]
length = len(p)
Max = 0
dp = np.zeros(length)
for i in range(1,length):
    dp[i] = max(p[i]-p[i-1]+dp[i-1],0)
    if(dp[i] > Max):
        Max = dp[i]
print(Max)

优化

在上面代码里，我们使用了一个长度为n的数组存储每次计算的收益，但实际上我们可以发现，算当天收益仅仅需要前一天卖出时收益这一个额外变量；并且前一天卖出的收益在这里使用一次后便没有用了。故我们可以考虑使用滚动数组，把空间复杂度压缩到常数级。

改良后的代码如下：

import numpy as np
p = [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]
length = len(p)
Max = 0
dp = 0 #使用滚动数组
for i in range(1,length):
    dp = max(p[i]-p[i-1]+dp,0)
    if(dp > Max):
        Max = dp
print(Max)

在改良的代码中，我们仅仅使用了一个dp的变量去记录若上一天卖出能得到的收益，并迭代找到最大的一个。如果你想要知道得到最大收益是需要什么时候买进和卖出，也只需要多添加两个变量在修改max的时候去记录而已。