偶遇DP问题

今天偶然遇到一个买卖股票最佳时机（best-time-to-buy-and-sell-stock）的问题。这个问题本身是个简单问题，暴力解法（寻找每种时间组合）和迭代法（寻找差值最大的波峰波谷）都可以解决该问题。如果用动态规划的方法需要稍微拐个弯。写个文章顺便复习一下Dynamic Programing。

问题描述：
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

上面意思就是：有个数组记录着每天的股票价格，你选择一天买选择一天卖（记为一次交易，当然是先买再卖）使得获利最多。利润为负就返回0.

递归方法解：

arr = [7, 1, 5, 3, 6, 4]
arr1 = [7, 6, 5, 4, 3, 2, 1]

def rec_opt(arr, i):
    if i == 1:                     #出口
        p = arr[i] - arr[0]
        return 0 if p<0 else p
    else:                         #迭代式
        A = arr[i] - min(arr[:i])
        B = rec_opt(arr, i-1)
        p = max(A, B)
    return 0 if p<0 else p

print(rec_opt(arr, len(arr)-1))#5
print(rec_opt(arr1, len(arr1)-1))#0

上面代码在Leetcode上因为内存的限制是不通过的。测试用例数组增大，递归的调用深度增大。递归方法解DP问题的关键是找到迭代式和迭代出口。而且递归方法通常会出现重叠子问题算法时间复杂度为O(2**n)，这时可以开辟一个数组记录子问题的解，避免重复计算，以空间换时间。但是在该问题中没有出现重叠子问题。就不转成迭代的方法了。