动态规划算法的研究

动态规划算法(Dynamic Programming)是一种非常常用和易考察的算法，尤其是在程序员面试的时候。大体上DP的实现方式有两种，一种是自下而上的，通常是可以抽象出表格的形式，通常非常容易写成循环体的形式。另外一种是备忘录式的，即自顶向下的，通常很容易写成递归的形式。动态规划的两个关键思路点是。1. 找到解决问题的最优子问题，什么意思呢？就是想要解决一个大问题，我们看能不能先找到它里面元素构成的子问题的最优解，通过这些子问题的最优解从而很快速的求出大问题的最优解，如果满足这个形式的问题，通常就可以考虑DP的求解了，如果找不到这样的求解模式，很大可能是我们设置的子问题的形式上需要做一些转变。2. 重叠问题的记录，在1可以的情况下，我们再思考重叠问题该以何种形式存储，1维list还是2维，存储的是index还是value还是其他复杂的表示。有了这些基础思路，我们开始做题，实战出真知嘛。

股票的售卖问题 Leetcode 123

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        length = len(prices)
        if length < 2:
            return 0
        dp1 = [0 for i in range(length + 1)]
        dp2 = [0 for i in range(length + 1)]
        r1 = [0 for i in range(length + 1)]
        r2 = [0 for i in range(length + 1)]
        dp1[0] = dp1[1] = 0
        dp2[length] = dp2[length - 1] = 0
        r1[0] = r1[1] = 0
        r2[length] = r2[length - 1] = 0

        for x in range(2, length + 1):
            dp1[x] = max(dp1[x - 1] + prices[x - 1] - prices[x - 2], prices[x - 1] - prices[x - 2])
            r1[x] = max(r1[x - 1], dp1[x])
        for y in range(length - 2, -1,-1):
            dp2[y] = max(dp2[y + 1] + prices[y + 1] - prices[y], prices[y + 1] - prices[y])
            r2[y] = max(r2[y + 1], dp2[y])
        sum = 0
        for k in range(length + 1):
            sum = max(sum, r1[k] + r2[k])
        return sum