动态规划(单状态dp+多状态dp)、贪心算法 2019-09-30（未经允许禁止转载）

1.part1 绪论计算机是有限状态机

计算机本质上是一台有限状态机，只能根据已经计算过的状态集合（calculated state set），利用状态转移函数（state transfer function），来计算下一个状态（next state）

动态规划就是如此，利用已经计算过的状态和状态转移方程，来求解目标状态的值

这里要讨论的是一类问题，我将这类问题叫做行为状态树（行为状态图更恰当）问题（个人定义，方便自己理解）如图：

行为状态树

事实上，把行为状态树变为行为状态图更为恰当。例如可能存在这样的情况，图中的状态1也可以通过某个action转移到状态2，而不是相互隔离的关系。由于一开始理解尚不全面，现在更正为行为状态图

对于行为状态图问题，我们总是不能一步到位地得出问题当前阶段的目标状态的通项公式，看起来只能遍历所有的情况，也就是穷举来寻求目标解了

但是，如果当前状态和之前的若干个更小的状态可以建立起【递推关系】，而我们又把问题的每一个中间状态都记录下来，这样，求解当前状态的值就转化成了求解之前的若干个更小状态的值，自顶向下的递归或者自底向上的递推，都可以轻松解决。因此，【找到问题与子问题之间的状态递推式是关键】

2.part2 动态规划的内涵和特征

什么是最优子结构

问题分解成若干个子问题后，可以通过【子问题的最优解】，推导出问题的最优解。也就是，最优解必须可以由之前的最优解推出

什么是重叠子问题

注意，不要将重叠子问题等同于相等子问题。重叠子问题是指涉及的计算有部分重叠或者完全重叠的子问题，如子问题A计算自然数1到5的和，子问题B计算自然数0到6的和，那么AB就是存在计算重叠（部分重叠）的
那么，因为存在重叠的子问题，动态规划对每个子问题只解决一次，然后将解存储起来（字典、数组或者单变量，视具体问题而定），等下次需要这个子问题的解时，直接取出即可，不需反复计算。另外，当存在重叠子问题时，就一定满足最优子结构性质

什么是无后效性（without aftereffect）

通俗地理解就是，“未来与过去无关，只和现在有关。现在屏蔽了过去，一切从现在出发”。某阶段的状态一旦确定，此后过程的演变则不再关心此前各阶段的状态及决策，只关心当前的状态是怎样的。例如我们的人生就是无后效性的，我们大学毕业找什么样的工作，只关心我们毕业时的学校文凭、知识水平等，并不关心我们之前到底上了什么小学、初中、高中

现在看一下动态规划是什么东东

先记住，A.动态规划的目的，是为了求最优解，即求最值，B.当前问题和子问题通过状态转移方程形成图结构

动态规划（Dynamic programming，DP）

动态规划核心是穷举，但它的穷举有点特别，因为这类问题存在「重叠子问题」，暴力穷举产生了大量的重复计算，效率极其低下，需要「备忘录」或者「DP table」来优化穷举过程，避免重复计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值
- （敲黑板，重点）
  通过建立当前问题与之前规模更小的若干个问题间的【递推式】（注意：动态规划的递推式可以是跳跃式的，也可以是相邻问题规模间的递推），将求解问题转化为求解若干个子问题，直到子问题的解已知（即递归出口）；并且这一系列子问题会存在重叠，我们对子问题首次计算后，将对应的解保存起来，避免下次又进行重复计算

3.part3 动态规划的两种写法：

A.到哪里去（迭代法、自底向上法、状态表法、递增规模法。【我个人喜欢这种写法，能体现dp的思想】）

#####################################################
1.定义子问题要求解什么最XX解。一般而言，首先考虑原问题求啥，子问题就求啥；如果这样不能建立状态转移方程，再考虑原问题可以转化为求啥，然后考虑子问题。无论如何，子问题必须要求解一个最XX
2.写出问题与子问题间的状态转移方程，构造dp数组。dp数组的每个元素对应不同规模子问题的最XX解
3.写出dp table的base case
4.确定dp table的填空方向
#####################################################

B.从哪里来（递归法、自顶向下法、状态转移方程法、缩小规模法）
从哪里来，就是不断回溯到当前问题的上一阶段，不断缩小问题规模，直到达到起点为止。这种情况下，考虑的方向就是通过状态转移方程，以递归的方式不断缩小问题规模
灵活的是，问题的起始点和结束点是相对的，从A到B，也可以看作从B到A，因此可以说从A到B去，B从A来；也可以说从B到A去，A从B来

4.单状态dp问题与多状态dp问题

4.1 单状态dp问题

单状态dp问题，指一个规模问题下只存在一种状态，我们只需要关注这一种状态的转移，就可以求解目的问题。如最长路径问题、最短路径问题、最大和问题、最小和问题、寻路总数等这一类简单的加法或计数问题

先看5个单状态的动态规划例子
1).【计算数字塔从上到下所有路径中和最大的路径】
数字塔是第i行有i个数字组成，从上往下每个数字只能走到他正下方数字或者右下方数字，求数字塔从上到下所有路径中和最大的路径，如有下数字塔：

3
1 5
8 4 3
2 6 7 9
6 2 3 5 1

最大路径是3-5-3-9-5，和为25。我们可以分别从自顶向下和自底向上两种角度去解。以1层为底，5层为顶：

自顶向下
定义max(i, j, n)为第i行第j个元素到第n层的最大路径函数
value(i, j)为第i行第j个元素的值
关键：通过状态转移式缩小问题规模

# 用于存放各子问题的最优解的全局字典，避免重复计算
sub_questions = {}
def max(i,j,n):
    #递归出口
    if i == n: 
        return value(i, j)
    k = 'max%s%s%s' % (str(i), str(j), str(n))
    # 如果当前子问题的解在字典里，直接返回；否则求出后放入字典再返回
    if k not in sub_questions:
        # 这是最关键的状态转移式，缩小问题规模
        sub_questions[k] = value(i,j) + max(max(i+1, j, n), max(i+1, j+1, n))
    return sub_questions[k]

因此，所求 = max(1,1,5) = value(1,1) + max(max(2,1 5), max(2,2,5))
然后不断递归，直到进入i == n递归结束

自底向上（recommended）
1.定义子问题的解。原问题求首层到尾层的最大路径，那么考虑子问题也是求首层到某层最大路径，但这样难以找到两者间的关系；考虑拆分原问题，求解原问题等于求解max(首层到尾层各个位置的最大路径)，发现这样好找递推关系，那么【子问题就是求解首层到当前位置的最大路径】
2.状态转移方程。规划一张二维状态表dp，dp[i][j]表示首层到第i行第j个元素的最大路径，则dp[i][j] = value(i+1,j+1) + max(dp[i - 1][j], dp[i - 1][j - 1])
3.确定base case。dp[0][0] = value(1,1)
4.确定dp table填写的方向。由状态转移方程，dp table填写的方向为从上到下，从左到右

过程可视化如下：

3                            3                            3                             3

1    5                       4    8                       4    8                        4    8

8    4    3                  8    4    3                  12   12  11                   12   12   11  

2    6    7    9             2    6    7    9             2    6    7    9             14   18   19   20

6    2    3    5    1        6    2    3    5    1        6    2    3    5    1        20   20   22   25   21

# 初始化最大距离
max_route = 0
# 创造并初始化二维状态表
dp = [ [0 for j in range(i+1)] for i in range(n)]
dp[0][0] = value(1,1)
for i in range(1, n):
    j = 0
    while j <= i:
        # 如果是第一列，等于自身+上一位置的状态值
        if j == 0:
            dp[i][j] = value(i+1,j+1) + dp[i - 1][j]
        # 否则，等于自身+（上一位置和左上位置的最大状态值）
        else:
            dp[i][j] = value(i+1,j+1) + max(dp[i - 1][j], dp[i - 1][j - 1])
        max_route = max(max, dp[i][j])
        j += 1
return max_route

这里还能使用滚动dp数组优化，因为到某行的最大距离只与上一行的dp值有关

2). 【最大子序和】
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6

自底向上法思路：
对于这一题，我们很容易想到暴力穷举的思路就是从数组首个元素到最后一个元素做一次二维的遍历，求出所有可能的和，然后取最大。那么，哪些计算是重复并且可用于递推的呢？容易发现，以nums[i]结尾的最大子序和 = max(nums[i], 以nums[i-1]结尾的最大子序和 + nums[i])，而原问题的解恰好等价于以nums[i]结尾的最大子序和中的最大值（即：将原问题分治后，得到的各子问题间可以递推）。注意到，上面的斜体部分的值是暴力遍历中重复计算并且可用于递推的，因此我们用dp table把这些值存起来就game over了

# 自底向上法
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        max_sum = nums[0]
        # dp[i]记录以nums[i]结尾的最大子序和
        dp = [0 for i in range(L)]
        dp[0] = nums[0]
        for i in range(1, L):
            # 状态转移关系，注意千万别弄错
            dp[i] = max(dp[i-1] + nums[i], nums[i])
            # 找当前的最大和
            max_sum = max(max_sum, dp[i])
        # print(dp)
        return max_sum

后来看别人的提醒，发现每一次递推其实只用到上一次的最大子序和，再之前的值都不必保存，于是修改了一下，将数组dp存过往的所有值改成单变量dp_last存放上一个值，减少空间占用，代码如下：

# 自底向上法
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        L = len(nums)
        max_sum = nums[0]
        # dp_last记录递推中的上一个最大子序和
        dp_last = nums[0]        
        for i in range(1, L):
            # 状态转移关系
            dp_now = max(dp_last + nums[i], nums[i])
            # 找当前的最大和
            max_sum = max(max_sum, dp_now)
            dp_last = dp_now
        return max_sum

自顶向下
自顶向下的方法其实就是自底向上的逆方法，使用递归调用来实现。
本题先将原问题分成了N个子问题，N为传入的数组的长度，每个子问题是求以nums[i]结尾的最大序和，这时原问题就等价于求max(N个以nums[i]结尾的最大序和)。我们发现，这N个子问题之间是存在递推关系的！！！，所以原问题等价于保存递归中间过程值的、求以数组最后一个元素结尾的最大序和的问题
那么，容易想到，原问题的最优解可能在等价问题的递归中间过程出现，这里需要记录递归过程中产生的所有中间值，然后从这些中间值中寻找满足题意的最优解

max_sum = 0
# 求以nums数组最后一个元素结尾的最大序和
def maxendwith_nums_last_element(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    L = len(nums)
    global max_sum
    # 递归出口
    if L == 1:
        max_endwith_nums_last_element = nums[0]
        # 修改最大和
        max_sum = max(max_endwith_nums_last_element, max_sum)
        # 返回以数组最后一个元素结尾的序列最大和
        return max_endwith_nums_last_element
    # 状态转移式，缩小问题规模，不断递归
    max_endwith_nums_last_element = max(maxSubArray(nums[:-1]) + nums[-1], nums[-1])
    max_sum = max(max_endwith_nums_last_element, max_sum)
    # 返回以数组最后一个元素结尾的序列最大和
    return max_endwith_nums_last_element

def getMaxSum(nums):
    global max_sum
    maxendwith_nums_last_element(nums)
    return max_sum
        
print(getMaxSum([-2,1,-3,4,-1,2,1,-5,4]))
>>> 6

3). 爬n 阶楼梯，每次可以爬 1 或 2 个台阶，求共有多少种不同的方法
输入： n 正整数
输出：method_count 正整数
如：
输入：2
输出：2
因为有两种方法
1】 1 + 1
2】直接2

这题比较简单，直接写出自顶向下递归的初始代码：

# 自上而下递归，未保存递归过程中的重复值
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n > 0:
            if n == 2:
                return 2
            elif n == 1:
                return 1
            else:
                # 递归关系，将当前规模n与子规模n-1, n-2联系在一起，从而不断缩小问题规模
                return self.climbStairs(n-1) + self.climbStairs(n-2)
        else:
            print('阶梯数必须为正')

以上代码提交后，当输入n = 38时，会出现超出时间限制的问题，因为我们在递归过程中，对很多子问题进行了重复计算。由于递归树的结构特性，耗费的时间和空间会随着问题规模的增长指数级地增长

使用全局变量将递归过程中重复的值存起来，供各个递归时使用。优化代码如下：

# 自上而下递归，使用全局变量method_count字典保存递归过程中所有子问题的值
method_count = {}
class Solution(object):    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        global method_count
        if n > 0:
            # 总是先判断要获取的值是否已经被计算保存，没有则计算并保存
            if str(n) not in method_count:
                if n == 2:
                    method_count[str(n)] = 2
                elif n == 1:
                    method_count[str(n)] = 1
                else:
                    count = self.climbStairs(n-1) + self.climbStairs(n-2)
                    method_count[str(n)] = count
            return method_count[str(n)]
                
        else:
            print('阶梯数必须为正')

自底向上的也很好写，并且只需要保留2个变量存储中间值，理论上应该减少了空间消耗：

# 自底向上递推，每次只保留和更新2个值a、b
class Solution(object):    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 1
        b = 2
        if n == 1:
            return a
        if n > 2:
            for i in range(2, n):
                b, a = a + b, b
        return b

4). 爬虫位于一个 m x n 网格的左上角第一个网格内，m 为列数，n为行数。爬虫每次只能向下或者向右移动一步，则达到网格的右下角最后一个网格共有多少条不同的路径？
直接贴代码吧，写了这么多字也有感觉了

# 爬虫位于一个 m x n 网格的左上角第一个网格内，m 为列数，n为行数。
# 爬虫每次只能向下或者向右移动一步，则达到网格的右下角最后一个网格共有多少条不同的路径？


# 法一 利用排列组合知识解答
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        total_step = m+n-2
        a = 1
        for i in range(m, total_step+1):
            a = a*i
        b = 1
        for i in range(1, n):
            b = b*i
        return a/b


# 法二 自顶向下的动态规划
dict_value = {}
class Solution(object):    
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        global dict_value
        # 当只能向下或者向右时，只有一条路可以走
        if m == 1 or n == 1:
            return 1
        # 其余的情况下，先查字典看看当前问题有没有被计算后存储下来，无则计算后存入字典
        if "%s %s" % (m, n) not in dict_value:
            # 递归关系
            dict_value["%s %s" % (m, n)] = self.uniquePaths(m, n-1) + self.uniquePaths(m-1, n)
        return dict_value["%s %s" % (m, n)]


# 法三 自底向上的动态规划，这里通过dp状态表实现。
# 注意，通过状态表的话，每一个状态都相互不重复，每一个状态都要保存，所以相当于自底向上穷举了
class Solution(object):    
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 创建状态表
        dp = [[0 for i in range(m)] for j in range(n)]
        # 初始化起始状态，到达第一排或第一列的任意点都只有一种走法
        # 初始化第一行
        dp[0] = [1 for i in range(m)]
        # 初始化第一列
        for i in range(n):
            dp[i][0] = 1
        # print(dp)
        if m > 1 and n > 1:
            # 利用递推关系，逐步填写状态表
            for i in range(1, n):
                for j in range(1, m):
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[n-1][m-1]

5). 整数拆分。将一个整数拆分为多个(至少)整数，使拆分后的整数之积最大
思路：看到【大整数拆成小整数】，大整数到小整数，这就是状态转移方程的味道

# 维护一个一维dp数组，dp[i]表示整数i拆分后积的最大值。通过dp[i] = max( [max(dp[j], j) * max(dp[i-j], i-j)] )进行状态转移
class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for i in range(n+1)]
        # 初始化dp数组
        dp[1] = 1
        dp[2] = 1
        for i in range(3, n+1):
            ## 状态转移方程 ##
            possible_ans = [max(dp[j], j)*max(dp[i-j], i-j) for j in range(1,i//2+1)]
            dp[i] = max(possible_ans)
            ## 状态转移方程 ##
        return dp[n]

此外，本题还可通过数学方法求解。设整数 a = n*x，那么b = x^n = x^(a/x) = (x^(1/x))a，而x^(1/x)的极限为e约为2.718，因此应该尽可能拆分成整数3，拆不了3再拆成2

另外还有两道经典的动规问题，在这里

再加一道题
leetcode221 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
例如：

思路：
当我们判断以某个点为正方形右下角时最大的正方形时，那它的上方，左方和左上方三个点也一定是某个正方形的右下角，否则该点为右下角的正方形最大就是它自己了。这是定性的判断，那具体的最大正方形边长呢？

我们知道，该点为右下角的正方形的最大边长，最多比它的上方，左方和左上方为右下角的正方形的边长多1，最好的情况是是它的上方，左方和左上方为右下角的正方形的大小都一样的，这样加上该点就可以构成一个更大的正方形。但如果它的上方，左方和左上方为右下角的正方形的大小不一样，合起来就会缺了某个角落，这时候只能取那三个正方形中最小的正方形的边长加1了。假设dpi表示以i,j为右下角的正方形的最大边长，则有 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1当然，如果这个点在原矩阵中本身就是0的话，那dp[i]肯定就是0了

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        # 可以维护一个dp二维数组，dp[i][j]表示matrix[i][j]为正方形右下角的最大正方形的边长
        # 这里进行了一些优化，选择原地修改matrix数组替代dp数组
        m = len(matrix)
        n = len(matrix[0])
        res = 0
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
                if matrix[i][j] == 1:
                    res = 1

        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] != 0:
                    matrix[i][j] = min(matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
                    res = max(res, matrix[i][j])
        return res**2

4.2.多状态dp问题

多状态dp问题，指一个规模问题下存在多种状态，我们需要联合关注多种状态间的相互转移，才可以求解目的问题。经典的多状态dp问题是leetcode 309 最佳买卖股票时机含冷冻期，每一天都有3种状态：买入，卖出，不持有股票空等-冷冻，第i天这3种状态下的最大利润，都需要依赖第i-1天的这3种状态来推导

leetcode#### 152. 乘积最大子数组
给一个整数数组 nums ，找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字，正负数和0都可能出现），返回该子数组所对应的乘积
解法1：
由于求的是乘积，因此我们应该在保证相乘的数中负数的个数为偶数个的前提下，尽可能地多相乘非0数。因此，数组中的0实际上把数组进行了分割，对于被分割出来的每一段（只含非0数），都在保证相乘的数中负数的个数为偶数个的前提下，尽可能地多相乘。
当一个数组中没有0存在，则分为两种情况：
1.负数为偶数个，则整个数组的各个值相乘为最大值；
2.负数为奇数个，则从左边开始，乘到最后一个负数停止有一个“最大值”，从右边也有一个“最大值”，比较，得出最大值。
取所有乘积中最大的一个

代码怎么实现呢？先计算从左到右的相乘的最大值，碰到0置0；再计算从右到左的最大值，碰到0置0；再将两组最大值相比。妙啊！！

class Solution:
    def maxProduct(self, A):
        B = A[::-1]
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(A),max(B))

动态规划思路：
搞一个一维dp数组，dp[i]需要记录【两个值】，或者说记录【两个状态】，一个为以nums[i]结尾的子数组的最大值，一个为以nums[i]结尾的子数组的最小值。为啥？因为数组里有负数存在，如果nums[i+1]是正数，那么它需要以nums[i]结尾的子数组的最大值；如果nums[i+1]是负数，那么它需要以nums[i]结尾的子数组的最小值

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # dp数组, dp[i]包含2个值，以nums[i]结尾的子数组的乘积的最大值和最小值
        dp = [[] for i in range(len(nums))]
        # 初始化dp
        dp[0] = [nums[0],nums[0]]
        ans = float('-inf')
        ans = max(nums[0], ans)
        for i in range(1, len(nums)):
            # 状态转移方程
            max_multi = max(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])
            min_multi = min(dp[i-1][0]*nums[i], dp[i-1][1]*nums[i], nums[i])
            # 状态转移方程
            dp[i] = [max_multi, min_multi]
            ans = max(max_multi, ans)
        return ans

多状态dp问题下，dp table需要保持多个状态。更本质地说，有多少个状态，就需要维护多少个dp table

leetcode 309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
这也是一道多状态dp问题。多状态dp问题可以使用一个dp数组，每个存储单元存储多个状态；亦可以使用多个相互关联的dp数组，每个数组的存储单元存储各自负责的状态。本题就使用了3个关联的dp数组，相对更加直观

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        # 每一天都有3种状态，买/卖/不操作，分别用buy/sell/freeze数组标记
        # buy[i]表示在第i天进行买入后的最大总收益
        # sell[i]表示在第i天进行卖出后的最大总收益
        # freeze[i]表示在第i天混吃等死的最大总收益

        # 1.首先显然有freeze[i] = max(buy[i-1], sell[i-1], freeze[i-1])的关系式，即【今天混吃等死的收益 = max(昨天混吃等死收益，昨天买入收益，昨天卖出收益)】
        # 这里可以优化一下，因为buy[i-1]永远小于freeze[i-1]。为啥？因为不管前面几天怎么样，要使截至当前收益最大，肯定今天不能再花钱去买了，啥都不干就没有支出，手里的钱肯定更多
        # 所以，freeze[i] = max(sell[i-1], freeze[i-1])

        # 2.然后，sell[i]也可以很自然地推出，sell[i] = prices[i] + max(buy[:i])
        # 3.最后是buy[i]，根据冷冻期设定，buy[i] = freeze[i-1] - prices[i]

        l = len(prices)
        if l <= 1:
            return 0
        
        buy = [0 for i in range(l)]
        sell = [0 for i in range(l)]
        freeze = [0 for i in range(l)]
        buy[0] = - prices[0]
        for i in range(1, l):
            buy[i] = freeze[i-1] - prices[i]
            sell[i] = prices[i] + max(buy[:i])
            freeze[i] = max(sell[i-1], freeze[i-1])
        return max(sell[-1], freeze[-1])

另一种dp写法：
上面的dp table中，以buy为例，buy[i]表示在第i天进行买入后的最大总收益，这里换一种定义方式，buy[i]表示截至第i天时买入为最后状态下所对应的最大总收益，同理有sell[i]和freeze[i]
赋予dp的定义不同，状态转移方程也就不同。于是，新的dp代码如下。注意，由于sell[i] = max(sell[i-1], prices[i] + buy[i-1])，相比上面求sell[i]的O(n)时间复杂度，这里做到了O(1)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        # xxx[i]表示到第i天为止的最后一个动作是xxx时的最大利润，【买入，卖出，不持有光等待-冻结】
        buy, sell, freeze = [[0 for _ in range(n)] for i in range(3)]
        buy[0] = -prices[0]
        for i in range(1, n):
            buy[i] = max(buy[i-1], freeze[i-1] - prices[i])
            sell[i] = max(sell[i-1], prices[i] + buy[i-1])
            freeze[i] = max(freeze[i-1], sell[i-1])    
        # print(buy, freeze, sell)
        return max(sell[-1], freeze[-1])

LCP 19. 秋叶收藏集

给定一个仅包含r和y的字符串，要求整体形成ryr的3部分，即左边是连续的r，中间是连续的y，右边是连续的r，每一部分长度都>= 1。每次操作都可以将任意一个r变成y，也可以将y变成r。求形成ryr结构最少需要操作多少次

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n = len(leaves)
        #  
        #     dp table, f[i][j]中：
        #         i表示终止下标
        #         j表示3种状态：0-i位置属于左半边右端点，1-i位置为中间部分右端点，2-i为右半边右端点
        #     f[i][j] 表示 从0到i需要调整的叶子数
        #  
        f = [[0, 0, 0] for _ in range(n)]
        f[0][0] = int(leaves[0] == "y")
        # 第0个位置不可能是【中间部分或右半边】的右端点，第1个位置不可能是右半边的右端点，置为无穷大
        f[0][1] = f[0][2] = f[1][2] = float("inf")

        for i in range(1, n):
            isRed = int(leaves[i] == "r")
            isYellow = int(leaves[i] == "y")
            f[i][0] = f[i - 1][0] + isYellow
            f[i][1] = min(f[i - 1][0], f[i - 1][1]) + isRed
            if i >= 2:
                f[i][2] = min(f[i - 1][1], f[i - 1][2]) + isYellow
        
        return f[n - 1][2]

part4 我对动态规划与贪心算法的对比理解

动态规划，本质上是【满足最优子结构和无后效性的问题】的【优化的穷举法】

贪心算法，本质上是“贪心”思想指导下的【定式规划】，或者说【定式决策】

传统的穷举法，一般都是brute force暴力计算所有情况下的目标值，而不考虑计算过程中是否存在某些值被重复计算的问题
贪心算法并非动态规划，反而是“固态规划”。贪心与动规都需要满足最优子结构和无后效性，有些资料会由此认为贪心算法是一种特殊的动态规划，我认为不然。理由如下：
动态规划是优化过的穷举，本质上还是穷举，需要考虑所有子问题的最优解才能得到最终的最优解，然后将最优解作为决策的依据；
但贪心算法并不是穷举，它固定地考虑每一阶段到下一阶段的最优作为决策的依据，是“贪心”的定式，不是一个动态求最优解的过程。另外，贪心算法得到的是局部最优解

part5 贪心算法的应用

既然贪婪算法只能得到局部最优，那么它能发挥什么作用呢？---动态规划的替代品

贪婪算法(近似算法)在大部分情况下易于实现，效率高。当问题的规模很庞大时，动态规划往往面临极大的计算量，这时使用贪心算法可以高效地得到一个近似最优解，减少计算量的同时，得到的解也近似最优解

ps 写到了2019.9.30的最后一分钟，撤了撤了TT
欢迎各位大神一起交流偶

此文为作者原创，未经许可，禁止转载

最后编辑于：2020.10.01 20:41:41

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,602评论 6赞 481
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,442评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 152,878评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,306评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,330评论 5赞 373
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,071评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,382评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,006评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,512评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,965评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,094评论 1赞 333
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,732评论 4赞 323
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,283评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,286评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,512评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,536评论 2赞 354
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,828评论 2赞 345