和分治法一样，动态规划（dynamic programming）是通过组合子问题而解决整个问题的解。

分治法是将问题划分成一些独立的子问题，递归地求解各子问题，然后合并子问题的解。

动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。

此时，分治法会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子问题只求解一次，将其结果保存起来，从而避免每次遇到各个子问题时重新计算答案。

适用范围

最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。

最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。

1.问题中的状态满足最优性原理。

2.问题中的状态必须满足无后效性。

所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。

动态规划算法的设计

两种方法：

自顶向下（又称记忆化搜索、备忘录）：基本上对应着递归函数实现，从大范围开始计算，要注意不断保存中间结果，避免重复计算

自底向上（递推）：从小范围递推计算到大范围

递归方程+边界条件

动态规划问题汇总

1. 子序列问题

爬楼梯问题 (leetcode 70题)

一个人每次只能走一层楼梯或者两层楼梯，问走到第80层楼梯一共有多少种方法。

到第n步有两个选择

从第n-2步一次跨两步到第n个位置

或者从第n-1步跨一步到第n个位置

(不要考虑从第n-2跨一步到n-1再跨一步到n, 因为那也算是经过n-1)

所以此时只要计算前面到n-2步共可能有多少总走法, 和到n-1共有多少总走法, 然后求和就行

然而第n-2步也可以由第n-4和第n-3两种走法, 以此类推直到第n=2步时

设DP[i]为走到第i层一共有多少种方法，那么DP[80]即为所求。很显然DP[1]=1, DP[2]=2（走到第一层只有一种方法：就是走一层楼梯；走到第二层有两种方法：走两次一层楼梯或者走一次两层楼梯）。同理，走到第i层楼梯，可以从i-1层走一层，或者从i-2走两层。很容易得到：

递推公式：DP[i]=DP[i-1]+DP[i-2]

边界条件：DP[1]=1 DP[2]=2

step=[None]*80
step[0],step[1],step[2]=0,1,2
for i in range(3,80):
    step[i]=step[i-1]+step[i-2]
print(step)

除此之外, 还可以用递归算法

而且其符合斐波那契数列的定义:

Fib(n)=Fib(n−1)+Fib(n−2)

故用程序写的话就是:

def climbStairs(n):
        if n<3:
            return n
        second,first,result=1,2,3
        for i in range(3,n+1):
            result=first+second
            second,first=first,result
        return result

或者直接通过斐波那契公式求第n个数:

最长上升子序列

最长上升子序列就符合这一特性。我们要求n个数的最长上升子序列，可以求前n-1个数的最长上升子序列，再跟第n个数进行判断。求前n-1个数的最长上升子序列，可以通过求前n-2个数的最长上升子序列……直到求前1个数的最长上升子序列，此时LIS当然为1。

让我们举个例子：求 2 7 1 5 6 4 3 8 9 的最长上升子序列。我们定义d(i) (i∈[1,n])来表示前i个数以A[i]结尾的最长上升子序列长度。

前1个数 d(1)=1 子序列为2；

前2个数 7前面有2小于7 d(2)=d(1)+1=2 子序列为2 7

前3个数 在1前面没有比1更小的，1自身组成长度为1的子序列 d(3)=1 子序列为1

前4个数 5前面有2小于5 d(4)=d(1)+1=2 子序列为2 5

前5个数 6前面有2 5小于6 d(5)=d(4)+1=3 子序列为2 5 6

前6个数 4前面有2小于4 d(6)=d(1)+1=2 子序列为2 4

前7个数 3前面有2小于3 d(3)=d(1)+1=2 子序列为2 3

前8个数 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列为2 5 6 8

前9个数 9前面有2 5 6 8小于9 d(9)=d(8)+1=5 子序列为2 5 6 8 9

d(i)=max{d(1),d(2),……,d(i)} 我们可以看出这9个数的LIS为d(9)=5

所以我们的程序就从第一个元素开始, 首先第一个元素的长度为1, 然后第二个元素比第一个元素大, 所以第二个元素的长度等于第一个的长度加1, 第三个比前两个都小, 长度为1,第四个比第三个和第一个元素都要大, 所以找出第三个和第一个元素所对应长度中较大的那个然后加1作为第四个元素的长度, 以此类推

#一看到这题, 首先应该想到带memorization的方法, 一步一步查前一步的memo中的对应元素就行
def lis(seq):
    length=len(seq)
    if not length:return 0
    memo=[1]*length
    for i in range(length):
        maximum=1
        for j in range(i):
            if seq[j]<seq[i]:
                maximum=max(maximum,memo[j]+1)
        memo[i]=maximum
    return max(memo)



#这种写法不好, 是之前写的, 不过暂时留着吧
def solution(array):
    distance=[1]*len(array)
    if len(array)==0:
        return 0
    for i in range(len(array)):
        cur_small=[]
        for j in range(0,i):
            if array[i]>array[j]:
                cur_small.append(j)
        try:
            distance[i]=max(list(map(lambda k:distance[k],cur_small)))+1
        except:
            #此处是防止当前值前没有任何值小于当前值, 会出现max的数组是空的报错
            pass
    return max(distance)

最长公共子序列

给定两个序列X和Y，称序列Z是X和Y的公共子序列如果Z既是X的一个子序列，又是Y的一个子序列。例如，如果X={a,b,c,b,d,a,b} Y={b,d,c,a,b,a} 那么序列{b,c,a}就是X和Y的一个公共子序列，但是它并不是X和Y的最长公共子序列，因为它的长度为3。而同为X和Y公共子序列的{b,c,b,a}，长度为4，因为找不到长度为5或更大的公共子序列，所以X和Y的最长公共子序列长度就为4。

这道题应该首先想到two pointer的解法, 接着想到可以用memorization记录之前的公共子序列长度, 因为是two pointer, 所以建立二维memo矩阵

假设两个序列数组分别为a，b。定义f(i,j)为计算到a数组第i个数、b数组第j个数时所得到的最长公共子序列的长度。这时有两种情况：

1.假如a[i]=b[j]，那么f(i,j)=f(i-1,j-1)+1

2.假如a[i]!=b[j]，那么f(i,j)=max(f(i-1,j),f(i,j-1))

边界条件为：f(i,0)=0 1<=i<=len(a)

f(0,j)=0 1<=j<=len(b)

设 X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是两个序列

1）如果 xn=ym

**即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)
**

****2）如果xn != ym**
**

****它产生了两个子问题：LCS(Xn-1，Ym) 和 LCS(Xn，Ym-1)

LCS(Xn-1，Ym)表示：最长公共序列可以在(x1,x2,....x(n-1)) 和 (y1,y2,...yn)中找。

LCS(Xn，Ym-1)表示：最长公共序列可以在(x1,x2,....xn) 和 (y1,y2,...y(n-1))中找。

递推公式： （分最后一个相同和最后一个不同来分析）  1.当i或j等于0，MaxLen(i,j)==0;  2 当s1和s2的最后一个字符相同时，MaxLen(i,j)=MaxLen(i-1,j-1)+1;  3 当s1和s2的最后一个字符不同时，MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );

def solution(str1,str2):
    str1_list,str2_list=[*str1],[*str2]
    str1_len,str2_len=len(str1),len(str2)
    maxlen=[[0 for j in range(str2_len+1)] for i in range(str1_len+1)]
    #if str1_list[-1]==str2_list[-1]:flag=True
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
            if str1_list[i-1]==str2_list[j-1]:
                #此处改为maxlen[i][j]=max(maxlen[i-1][j-1]+1,maxlen[i-1][j],maxlen[i][j-1])也可
                maxlen[i][j]=maxlen[i-1][j-1]+1
            else:
                #因为每次都是max(maxlen[i][j-1],maxlen[i-1][j]), 所以在前面匹配上的可以通过maxlen[i][j-1]或者maxlen[i-1][j]一步一步传到后面
                maxlen[i][j]=max(maxlen[i][j-1],maxlen[i-1][j])
    return maxlen[-1][-1]

子序列最大累积Product问题(Leetcode 152)

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

/*
这个问题最麻烦的就是, 需要考虑负数, 即加入输入序列是[-2,1,-3], 那么最终答案是6, 如果没有负数的话, 递推公式只需要 grid[i]=max(grid[i-1]*nums[i],nums[i]) 即可, 即用递推公式决定是否继续之前的累积下去, 还是从现在开始重新开始新一轮的累积, 因为这个递推公式是从0开始的, 所以可以认定每一轮都能选择到最优的累积方式。

首先我们开始nums[0], grid[0]=nums[0]; 然后grid[1]=max(grid[0]*nums[1],nums[1]), 在这一步中grid[1]的最后选出来的结果肯定是最优的; 接着grid[2]=max(grid[0]*nums[1],nums[1]), 因为grid[1]是最优的, 所以这么选出来的grid[2]肯定也是最优的, 注意, 我们在思考grid[2]的时候 不需要 又想grid[1]是否是最优的呢, 因为我们一步一步迭代过来的, grid[1]肯定是最优的, 所以我们在思考grid[2]的时候就假定grid[1]已经是最优的了。

在上面这个过程中, 我们发现其实grid这个矩阵可有可无, 我们在第i轮只需要知道grid[i-1]的大小, 而不需要考虑grid[i-2],grid[i-3]...之类的, 那么我们可以专门拿出一个变量就存上一轮的grid[i-1], 因此连grid矩阵都不需要了

可是, 上述讨论的这些内容, 仅仅是在序列中所有数都为正的情况下, 如果是包括负数, 因为有负负得正的情况, 所以像[-2,1,-3]这种情况, 按照上面的方法就错了, 因为在第二轮的时候就会把-2扔了, 将1保留下来作为当前轮的状态。

那么我们知道负数是小于0的, 而正数是大于0的, 所以我们在保存上一轮的状态时, 保留两个值, 一个是上一轮状态的最小值, 一个是最大值, 因为如果有负数出现的话上一轮状态最小值肯定是负数。然后上一轮最小状态和最大状态之间交叉求值。 

譬如[2,-1,3,-5,4], 用past_min和past_max表示上一轮的累积最小值和最大值

第一轮, 2为当前循环值, past_min=2, past_max=2
第二轮, -1为当前循环值, past_min=-2, past_max=-1
第三轮, 3为当前循环值, past_min=-6, past_max=3
第四轮, -5为当前循环值, past_min=past_max*-5=-15, past_max=past_min*-5=30      //进行了一次交叉, 因为碰到了负负得正的情况, past_min和past_max互换
第五轮, 4为当前循环值, past_min=-15*4=60, past_max=30*4=120


*/
int maxProduct(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        int maximum=nums[0],last_max=nums[0],last_min=nums[0];
        int temp_max;
        for(int i=1;i<nums.size();i++){
            temp_max=max(max(last_max*nums[i],nums[i]),max(last_min*nums[i],nums[i]));  //max(max(),max())能确保可以解决负负得正的情况
            maximum=max(temp_max,maximum);
            last_min=min(min(last_max*nums[i],nums[i]),min(last_min*nums[i],nums[i]));  //min(min(),min())能确保可以解决负负得正的情况
            last_max=temp_max;
        }
        return maximum;
    }     

2. 求难递推公式问题

Longest Valid Parentheses(Leetcode 32)

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

我们首先生成一个dp序列, 长度跟字符串长度相同, 将这个序列用0初始化, dp序列第i位置上的值代表在以i位置上元素结束的最长有效substring, 我们需要想明白这几点:

• [1] 如果第i位置上是‘(’的话那么一定dp[i]=0, 因为不会有以‘(’结尾的有效字符串

• [2] 根据上条原则, 仅当i位置上的字符为‘)’时dp[i]才有可能不为0

• [3] 对于最终Output大于等于2的字符串, 其中一定有两个相邻的字符分别为‘(’和‘)’, 即‘()’一定在字符串的某一处出现了

• [4] 思考这样一个例子: ‘( ( ( ) ) )’, 我们希望的是首先找到最里边的‘()’, 接着再向外面扩一层, 变为 ‘( ( ) )’, 以此类推

• [5] 对于复杂一些的例子譬如 ‘( ( ) ( ) )’, 假设这6个字符的下标分别为0到5, 假设该字符串用S表示, 首先我们先找到 S[1:3]=‘()’, 故dp[2]=2, 以此类推, 我么发现S[3:5]=‘()’, 此时我们希望dp[4]=4而不是2, 因为前面已经有一个相连的有效的字符串了即S[1:3], 那么此时我们可以认为dp[4]=dp[2]+2, 再来看最后一位S[5], 我们希望其能与S[0]匹配上, 那么此时我们希望跳过中间这4个, 我们发现dp[4]=4, 那么此时S[5-dp[4]-1]=S[0]

基于上述要求, 我们分两种情况讨论(我们只需要考虑S[i]=‘)’而S[i-1]取不同值得情况, 因为如果S[i]=‘(’的话dp[i]一定等于0):

• S[i]=‘)’同时S[i-1]=‘(’时, 此时字符串看上去是: ……(), 那么此时有(根据上述第5条): dp[i]=dp[i-2]+2

• S[i]=‘)’同时S[i-1]=‘)’时, 同时如果S[i-dp[i-1]-1]=‘(’的话 此时就是: **dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2, **即代表能和之前的连起来, 注意是dp[i-dp[i-1]-2], 因为dp[i-dp[i-1]-1]是等于0的( 因为该位置上是’(’, 此时dp等于0, 即上述第五条 )

def longestValidParentheses(s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        length=len(s)
        dp=[0]*length
        for i in range(1,length):
            if s[i]==')' and s[i-1]=='(':
              
                dp[i]= dp[i-2]+2 if i-2>=0 else 2
                
            elif s[i]==')' and s[i-1]==')':
                #此处大于0的判断会导致i-dp[i-1]-2=-1的情况发生, 但是其实没关系, 因为dp的值是从前往后赋的, 而dp初始化为0, 所以dp[-1]==0
                #不过如果将大于等于改为大于的话, 会导致当i-dp[i-1]-1==0时不进入if循环, 此时dp[i]的值无法+2
                if i-dp[i-1]-1>=0:
                    if s[i-dp[i-1]-1]=='(':
                        dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2
        return max(dp)

另一种解法是(Stack方法) :

• 首先发现第一个’()’, 然后向外扩展

• 每成功扩展一次(也就意味着当前连着的substring长度加上已经被pop出来成功连接的substring的长度再加2)

def lvp(seq):
    stack=[]
    cum,res=0,0
    for s in seq:
        if s=='(':
            stack.append('(')
        else:
            if stack:
                stack.pop()
                cum+=2
                res=max(res,cum)
            else:
                res=max(res,cum)
                cum=0
    return res

#下面这种写法直接将stack[-1]当做上边那种写法的cum
def longestValidParentheses(s):
        """
        :type s: str
        :rtype: int
        """
        stack = [0]
        longest = 0
        
        for c in s:
            if c == "(":
                stack.append(0)
            else:
                if len(stack) > 1:
                    val = stack.pop()
                    stack[-1] += val + 2
                    longest = max(longest, stack[-1])
                else:
                    stack = [0]

        return longest

3. 背包问题

3.1 简介

来自https://www.jianshu.com/p/25f4a183ede5

假设我们有n件物品，分别编号为1, 2...n。其中编号为i的物品价值为vi，它的重量为wi。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是W。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？问题结构如下图所示：

9960E20BF17B1BF2735BB0086C9AD6CB.png

这个问题其实根据不同的情况可以归结为不同的解决方法。假定我们这里选取的物品每个都是独立的，不能选取部分。也就是说我们要么选取某个物品，要么不能选取，不能只选取一个物品的一部分。这种情况，我们称之为0-1背包问题。而如果我们可以使用部分的物品的话，这个问题则成为部分背包(fractional knapsack)问题。这里我们只考虑0-1背包问题。

3.2 初步分析

对于这个问题，一开始确实有点不太好入手。一堆的物品，每一个都有一定的质量和价值，我们能够装入的总重量有限制，该怎么来装使得价值最大呢？对于这n个物品，每个物品我们可能会选，也可能不选，那么我们总共就可能有2^n种组合选择方式。如果我们采用这种办法来硬算的话，则整体的时间复杂度就达到指数级别的，肯定不可行。

现在我们换一种思路。既然每一种物品都有价格和重量，我们优先挑选那些单位价格最高的是否可行呢？比如在下图中，我们有3种物品，他们的重量和价格分别是10, 20, 30 kg和60, 100, 120。

0D5F1307CC777CEFDAD3C4EC6360C28D.png

那么按照单位价格来算的话，我们最先应该挑选的是价格为60的元素，选择它之后，背包还剩下50 - 10 = 40kg。再继续前面的选择，我们应该挑选价格为100的元素，这样背包里的总价值为60 + 100 = 160。所占用的重量为30, 剩下20kg。因为后面需要挑选的物品为30kg已经超出背包的容量了。我们按照这种思路能选择到的最多就是前面两个物品。如下图：

549CAF213ADCC06513E38168B3FE7A88.png

按照我们前面的期望，这样选择得到的价值应该是最大的。可是由于有一个背包重量的限制，这里只用了30kg，还有剩下20kg浪费了。这会是最优的选择吗？我们看看所有的选择情况：

D1496B280FE34EF6EA0CBACE88652AC9.png

很遗憾，在这几种选择情况中，我们前面的选择反而是带来价值最低的。而选择重量分别为20kg和30kg的物品带来了最大的价值。看来，我们刚才这种选择最佳单位价格的方式也行不通。

3.3 动态规划思路

既然前面两种办法都不可行，我们再来看看有没有别的方法。我们再来看这个问题。假设我们已经选择n个元素中的若干个来形成最优解，假定为k个。那么对于这k个元素a1, a2, ...ak来说，它们组成的物品组合必然满足总重量<=背包重量限制，而且它们的价值必然是最大的。因为它们是我们假定的最优选择，肯定价值应该是最大的。假定ak是在构造这个最优选择期间我们按照顺序放入的最后一个物品。它的重量为wk，它的价值为vk。既然我们前面选择的这k个元素构成了最优选择，如果我们把这个ak物品拿走，对应于k-1个物品来说，它们所涵盖的重量范围为0~(W-wk)。假定W为背包允许承重的量。假定最终的价值是V，剩下的物品所构成的价值为V-vk。这剩下的k-1个元素是不是构成了一个这种W-wk的最优解呢？

我们可以用反证法来推导。假定拿走ak这个物品后，剩下的这些物品没有构成W-wk重量范围的最佳价值选择。那么我们肯定有另外k-1个元素，他们在W-wk重量范围内构成的价值更大。如果这样的话，我们用这k-1个物品再加上第k个，(注意此处的重量限制是小于W-wk, 也就是说剩下的k-1个元素无论怎么构建, 只要满足重量限制在W-wk之内, 肯定最终是放得ak的) 他们构成的最终W重量范围内的价值就是最优的。这岂不是和我们前面假设的k个元素构成最佳矛盾了吗？所以我们可以肯定，在这k个元素里拿掉最后那个元素，前面剩下的元素依然构成一个最佳解。

现在我们经过前面的推理已经得到了一个基本的递推关系，就是一个最优解的子解集也是最优的。可是，我们该怎么来求得这个最优解呢？我们这样来看。假定我们定义一个函数c[i, w]表示到第i个元素为止，在限制总重量为w的情况下我们所能选择到的最优解。那么这个最优解要么包含有i这个物品，要么不包含，肯定是这两种情况中的一种。如果我们选择了第i个物品，那么实际上这个最优解是c[i - 1, w-wi] + vi (即前i-1个物品需要是满足w-wi重量的限制, 其中wi是当前这第i个物品的重量)。而如果我们没有选择第i个物品，这个最优解是c[i-1, w] (即前i-1个物品满足小于w的重量限制就可以了, 因为没有加第i个物品, 所以重量限制是w)。这样，实际上对于到底要不要取第i个物品，我们只要比较这两种情况，哪个的结果值更大不就是最优的么？

在前面讨论的关系里，还有一个情况我们需要考虑的就是，我们这个最优解是基于选择物品i时总重量还是在w范围内的，如果超出了呢？我们肯定不能选择它，这就和c[i-1, w]一样。

这里有一点值得注意，这里的wi指的是第i个物品的重量，而不是到第i个物品时的总重量。

另外，对于初始的情况呢？很明显c[0, w]里不管w是多少，肯定为0。因为它表示我们一个物品都不选择的情况。c[i, 0]也一样，当我们总重量限制为0时，肯定价值为0。

这样，基于我们前面讨论的这3个部分，我们可以得到一个如下的递推公式：

672E5F939DE183A29CDBD9675689F86C.png

有了这个关系，我们可以更进一步的来考虑代码实现了。我们有这么一个递归的关系，其中，后面的函数结果其实是依赖于前面的结果的。我们只要按照前面求出来最基础的最优条件，然后往后面一步步递推，就可以找到结果了。

我们再来考虑一下具体实现的细节。这一组物品分别有价值和重量，我们可以定义两个数组int[] v, int[] w。v[i]表示第i个物品的价值，w[i]表示第i个物品的重量。为了表示c[i, w]，我们可以使用一个int[i][w]的矩阵。其中i为物品的数量，而w表示最大的重量限制。按照前面的递推关系，c[i][0]和c[0][w]都是0。而我们所要求的最终结果是c[n][w]。所以我们实际中创建的矩阵是(n + 1) x (w + 1)的规格。

假设有5件物品，其重量分别是w={2，2，6，5，4}，价值分别是v={6，3，5，4，6}，背包容量为10。其C[i,w]矩阵显示如下(其中绿色的列代表当前限制重量, 即当限制重量为1,2,3,4,5,6,7,8,9,10时, 每一行代表当最大所能包含的物品数量分别为1,2,3,4,5时, 其在不同限制重量下最优解的价值):

3E20509209642CF33412E9F3936B1FBC.png

注意上图, 在没添加进物品4的时候, 只有物品123的时候, 在最大限重为6的情况下, 最高的价值为9, 在允许使用物品4后, 此时在限重6的情况下最大价值为12 (即物品4+物品0)

3.4 Python代码实现

下面代码实现了上图中的矩阵:

import pprint
def package(max_weight,weight_list,value_list):
    #这里横行的数量加一是为了确保之后每次grid[cur_item_index-1][cur_weight_limit]中的减一不会出现0-1=-1的情况
    #这里纵行的数量加一是因为要取到max_weight这个值, 因为如果不+1的话cur_weight_limit最大取到max_weight-1
    grid=[[0 for j in range(max_weight+1)] for i in range(len(value_list)+1)]
    weight_list,value_list=[0]+weight_list,[0]+value_list
    for cur_item_index in range(1,len(grid)):
        for cur_weight_limit in range(1,len(grid[0])):
            cur_item_weight=weight_list[cur_item_index]
            #注意此处是小于等于号
            if cur_item_weight<=cur_weight_limit:
                grid[cur_item_index][cur_weight_limit]=max(grid[cur_item_index-1][cur_weight_limit],\
                                        grid[cur_item_index-1][cur_weight_limit-cur_item_weight]+value_list[cur_item_index])
            else:
                grid[cur_item_index][cur_weight_limit]=grid[cur_item_index-1][cur_weight_limit]
    return grid

pprint.pprint(package(10,[2,2,6,5,4],[6,3,5,4,6]))

3.5 复杂度优化

以上方法的时间和空间复杂度均为 O(N*W)，其中时间复杂度基本已经不能再优 化了，但空间复杂度却可以优化到 O(W)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环 i=1..N，每次算出来 二维数组 f[i][0..W]的所有值。那么，如果只用一个数组 f[0..W]，能不能保证 第 i 次循环结束后 f[w]中表示的就是我们定义的状态 f[i][w]呢?f[i][w]是由 f[i-1][w]和 f[i-1][w-c[i]]两个子问题递推而来，能否保证在推 f[i][w]时(也 即在第 i 次主循环中推 f[w]时)能够得到 f[i-1][w]和 f[i-1][w-w[i]]的值呢? 事实上，这要求在每次主循环中我们以 v=V..0 的顺序推 f[w]，这样才能保证推 f[v]时 f[v-w[i]]保存的是状态 f[i-1][w-w[i]]的值。改进后的代码如下：

import numpy as np
def solve2(vlist,wlist,totalWeight,totalLength):
    resArr = np.zeros((totalWeight)+1,dtype=np.int32)
    for i in range(1,totalLength+1):
        #注意此处是从后往前, 这样一来res的值就能更新了, 就不像之前需要grid[i-1][j]的信息了
        #因为是从右往左, 每一次循环在j左边的元素其实都是上一轮即grid[i-1][:j]的元素, 起到了之前二维矩阵的效果
        #如果是从左往右, 那么每次grid[i][j]更新的值不是依靠grid[i-1][:j], 而是依靠grid[i][:j]了, 所以相当于重复更新了两边
        #之所以产生这个原因是因为j-wlist[i], 因为是减号, 所以要调用左边的元素, 那么从左往右更新的话, 右边的元素调用到的左边的元素都是更新过的
        #反之从右往左更新的话调用的元素都是上一轮更新的, 即这一轮还没更新过
        for j in range(totalWeight,0,-1):
            if wlist[i] <= j:
                resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
    return resArr[-1]

print(solve2([0,6,3,5,4,6],[0,2,2,6,5,4],10,5))

#简易版写法
def package(limit,weights,values):
    length=len(weights)
    #注意此处limit要+1因为要取到limit的值, 而不是最大值等于limit-1
    memo=[0]*(limit+1)
    for item in range(length):
        #此处注意要取到limit的值而不要limit-1
        for weight in range(limit,-1,-1):
            #此处要小于等于
            if weights[item]<=weight:
                memo[weight]=max(memo[weight-weights[item]]+values[item],memo[weight])
    return memo[-1]

3.6 进一步思考

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题 目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。 一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了 f[0]为 0 其它 f[1..W]均设为-∞，这样就可以保证最终得到的 f[N]是一种恰好装满背包的最 优解。
如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将 f[0..W]全部设为 0。
为什么呢?可以这样理解:初始化的 f 数组事实上就是在没有任何物品可以放入 背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能 被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属于未 定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何 容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状 态的值也就全部为 0 了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移 之前的初始化进行讲解。

3.7 扩展: 完全背包问题

完全背包问题与01背包问题的唯一差别就是完全背包问题允许每个物品无限次出现, 即每个物品有无限个数量, 那么其中一种想法就是扩展物品集, 假如一个物品的重量为w[i], 而限制的重量为W, 那么这个背包最多只能放下k=W/w[i]件该物品, 所以备选物品中只要有k个物品i就行了, 以此类推, 将备选物品集扩展, 然后再用01背包算法, 但是这样一来01背包算法的grid矩阵就会变得很大, 那么此时我们考虑改一下递推公式, 变为:

原来的公式中, 是, 而现在的是, 之前是按每次判断前i-1个元素中假如当前第i个元素和不加入当前第i个元素的最优解, 因为现在不是i-1了, 对于每一行而言, 这样一来整个grid矩阵形成的过程中每一个元素生成的过程可以调用该行前面的元素, 这样就代表元素可以反复使用, 而该行被调用的改行前面的元素又是之前调用的前面的前面的元素, 以此类推, 直到改行第一个非0元素, 这个非0元素判断的是加入第i个元素和不加入时前i-1个元素, 在相同的限重范围内, 哪个价值比较大

import pprint
def package(max_weight,weight_list,value_list):
    grid=[[0 for j in range(max_weight+1)] for i in range(len(value_list)+1)]
    weight_list,value_list=[0]+weight_list,[0]+value_list
    for cur_item_index in range(1,len(grid)):
        for cur_weight_limit in range(1,len(grid[0])):
            cur_item_weight=weight_list[cur_item_index]
            if cur_item_weight<=cur_weight_limit:
                grid[cur_item_index][cur_weight_limit]=max(
                                        grid[cur_item_index][cur_weight_limit-cur_item_weight]+value_list[cur_item_index],\
                                                grid[cur_item_index-1][cur_weight_limit])
            else:
                grid[cur_item_index][cur_weight_limit]=grid[cur_item_index-1][cur_weight_limit]
    return grid

pprint.pprint(package(10,[3,3,3,1],[6,3,3,1]))

除此之外, 按照上面改进的方法, 还有一种更巧妙的解法, 简化了空间复杂度, 即:

import numpy as np
def solve3(vlist,wlist,totalWeight,totalLength):
    resArr = np.zeros((totalWeight)+1,dtype=np.int32)
    for i in range(1,totalLength+1):
        #与之前的solve2相比唯一的区别就是solve2是倒序, 这个是正序
        #之前提到了, 从左往右更新每次更新都调用了之前已经更新过的, 这种调用就是确保了可以复用元素
        for j in range(1,totalWeight+1):
            if wlist[i] <= j:
                resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
    return resArr[-1]

print(solve3([0,6,3,5,1],[0,3,3,3,1],10,4))

4. 字符串类

拼接子串问题(Leetcode 97)

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", *s3* = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", *s3* = "aadbbbaccc"
Output: false

下面动图的逻辑如下:

• 首先根据最底下那串字符串, 底下字符串每向右移动一次选中一个字符C, grid中就向右移动一格变为grid[i][j]
• 如果这格中对应的上面的字符 stringUP[j]=C 或者等于左边的字符 stringLeft[i]中的任意一个的话(三者相等也是一样的) , 那么判断下一个条件, 如果不等于那这格的值肯定是False
• 上一条中如果等于其中一个的话, 则判断grid[i-1][j]和grid[i][j-1]的值, 如果上面的字符 stringUP[j]=C且grid[1][j-1]=True的话, 注意, 此处是当grid[i][j]=stringUp[j], 此时判断左边那位即grid[i][j-1]是否为True, 同理, 如果grid[i][j]=stringLeft[j]的话, 判断上一行的grid[i-1][j]是否为True, 如果满足的话, 那么此时格子的值就为True


39258A8831C9C63C32132D5E58F40CD1.jpg

左边那列代表当前用掉的值, 如果

我们来看下面这张图片, 在当前点grid[i-1][j]和grid[i][j-1]都是True，那代表什么意思呢:

• 我们先看它上面那个即grid[i-1][j], grid[i-1][j]左侧对应着a, 而其前面还有一个a, 此时代表当前由s1和s2组成的string的前两个为aa, 然后再看grid[i-1][j]上面对应的是b, b前面还有一个d, 那么意思即aa后面接的是db, 所以当前情况下, 由s1和s2部分拼接成的字符串为aadb, 那么此时回到grid[i][j], 此时如果再从左边那列中选出一个b的话, 拼接在aadb后, 就能得到aadbb, 刚好跟图片最底下的那行前五位一致, 所以是可行的, 此处是true
• 那么我们再看其左边那个, 即grid[i][j-1], grid[i][j-1]是怎么生成的呢, 由于grid[i][j-2]是False, 很显然不是由其生成的, 也就是说之前元素不是aab, 而是由grid[i-1][j-1]生成的, 也就是说, 先从左边列表将前两个取出来, 即aa, 然后从上边列表取一个d, 即aad, 然后光标再向下移一个, 移到了grid[i][j-1]的位置, 此处再从左边列表取出一个b, 此时形成了aadb, 那么此时这一行的b已经用过了, 光标只能向右移了, 所以到了grid[i][j], 即从上面那列再取一个b, 形成了aabdb, 符合最底下字符串的当前值
• 也就是说, 如果要到达grid[i][j]这个元素, 我们可以从其上面grid[i-1][j]为T的对应的序列aadb中加入一个从左边序列抽取出来的b, 或者从其左边grid[i][j-1]为T所对应的序列aadb中加入从上面序列抽取出来的b, 这是为了避免反复抽取, 譬如(其中L代表从左边序列抽取出来的, U代表从右边): a(L)a(L)d(U)b(L), 此时到达了grid[i][j], 但此时左边序列的b已经被抽取出去构成aadb了, 不能再从左边序列抽取b了, 所以要从上面序列抽取b, 所以要判断grid[i-1][j]=True并且StringUp(j)=b; 同理, a(L)a(L)d(U)b(U)到达grid[i][j]后就要判断左边序列的情况

6B4A70DA6729CABB100C6E5EDB15BAB4.png

代码如下:

#O(n)空间复杂度
def isInterleave3(s1, s2, s3):
    r, c, l= len(s1), len(s2), len(s3)
    if r+c != l:
        return False
    dp = [True for _ in xrange(c+1)]
    #这是在没有s1的情况下单独用s2匹配字符串, 因此底下的要写xrange(i,r+1), 这个+1是确保s1每一个字母都被匹配到
    for j in xrange(1, c+1):
        dp[j] = dp[j-1] and s2[j-1] == s3[j-1]
    #此处r要+1的原因是上面单独匹配了一次s2, 而s1需要从1开始计数, 为了能把s1整个列表都遍历完, 所以要用r+1
    for i in xrange(1, r+1):
        dp[0] = (dp[0] and s1[i-1] == s3[i-1])
        for j in xrange(1, c+1):
            dp[j] = (dp[j] and s1[i-1] == s3[i-1+j]) or (dp[j-1] and s2[j-1] == s3[i-1+j])
    return dp[-1]

除了上述方法外, 还可通过BFS和DFS求解, 在BFS和DFS那部分有介绍

最小编辑距离(Levenshtein)(Leetcode 72)

两个参考网站: https://people.cs.umass.edu/~mccallum/courses/cl2006/lect4-stredit.pdf 和 https://web.stanford.edu/class/cs124/lec/med.pdf

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character (Need 1 step)
2. Delete a character (Need 1 step)
3. Replace a character (Need 2 step)

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 4
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 8
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

也就是对字符操作, 共有三种操作, insert, delete或者replace, 此处leetcode原题是三种操作都只需要1步, 但正宗的是前两种操作各需要一步, replace需要两步, 所以改了一下上述leetcode中的输入和输出

在求解动态规划问题的时候，都需要回答以下几个问题:

• 状态是什么❓ 在最小编辑距离中，我们定义D[i][j]为长度为i的字符串X和长度为j的字符串Y的最小编辑距离，我们要求解的就是最终的状态D[m][n]
• 初始状态值是多少❓有了状态的定义，我们就可以找出初始状态的值，因为在动态规划中，我们要做的是求解最终的状态， 这必须依赖于初始状态和转移方程。一般来说，初始状态都是边界值，就是D[i][0]和D[0][j]。在最小编辑距离问题中，D[i][0]表示长度为i的字符串和长度为0的字符串的最小编辑距离，显然只能通过删除操作，得到长度为0的字符串，所以有D[i][0]=i。同理D[0][j]=j
• 转移方程❓转移方程是动态规划中的重点，这个方程应具体问题具体分析，在本问题中，看下面示意图:

72521E01A13E04174EC598E05BCCC45E.png

这里我用 # I N T E N T I O N 表示字符串X，# E X E C U T I O N表示字符串Y。假设现在要计算的是D[i][j]，此时i指向T,j指向E，我们要定义转移方程，也就是如何用已知的状态来推出现在的状态，换句话说，就是将当前状态D[i][j]用之前状态来求解。

此时我们只看字符串X和字符串Y的前4位元素, 即#INT和#EXE, 不要考虑之后的字符, 在如下讨论中分别叙述了红色, 黄色以及蓝色三种不同的方法

那么怎么表示呢？虽然这个方程需要具体问题具体分析得到，但是分析的过程一般是一样的，如何做分析呢？

1. 数型结合，可以先画出示意图，方便我们分析，如上面我画的这个示意图；
2. 转化化归，要知道，我们是想通过用已知来表示未知，所以在示意图画出来后，我们要明白要做的是将未知的D[i][j]转化为前面已知状态表示。
3. 分类整合,这里实际上有两个小步骤:

• 分类:用已知表示未知，或者从已知走向未知，路径往往不唯一！可以说在动态规划问题里肯定是不唯一的，也就是说D[i][j]可以有多条路径得到。这时候我们就要分类讨论，在这个问题中，我在示意图画出了三种颜色的线，分别表示三种不同的路径:

  • 红色: D[i][j]可以这样得到，先将X(1..i)转化为Y(1...j-1), 即相当于在前一个状态中Y(1…j-1)中插入一个Y(j),不要考虑插入Y(j)后面序列会往后移一位的事, 那是之后的步骤考虑的 , 此时应该求他们的最小编辑距离D[i][j-1]，然后呢插入Y(j)，所以，最后总的编辑距离为D[i][j] = D[i][j-1] + (insert)

  • 蓝色: D[i][j]可以这样得到，先将X(1..i-1)转化为Y(1…j)，此时应该求他们的最小编辑距离D[i-1][j]，删除X(i)，所以，最后总的编辑距离为D[i][j] = D[i-1][j] + 1 (delete)

  • 黄色: D[i][j]可以这样得到，先将长度为i-1的字符串转化为长度为j-1的字符串，此时应该求他们的最小编辑距离D[i-1][j-1]，然后呢做一下判断X(i)是否等于Y(j)，如果相等就不要做替换操作，否则需要做替换操作，所以，最后总的编辑距离为D[i][j] = D[i-1][j-1] + 0 if X(i) = Y(j) 或 D[i][j] = D[i-1][j-1] + 2 if X(i) != Y(j) 注意，替换操作编辑距离为2

• 整合: 这一步就是对上述所有路径求最小值(或者最大值)

所以最后的转移方程如下:

F46DBD4046C3E9519337B82DAAB2BDAB.png

因此, 得到的dp图如下:

3FE991955639A3D1ACE9FB3308B821FC.png

9415DEDCEED26423FB5DC19957B85C6A.jpg

那每个格子的移动代表什么呢, 如下是来自另一个参考文献的叙述图, 与上图是倒过来的关系:

6CF5CEEB503BB48E722F56DDA53FEF0E.png

我们以其中紫色的那个格子值为4的来作为例子, 可以这样理解, 该格子对应着的X字符是N, Y字符串是E, 此处可以认为由#INTEN转化为#E, 需要进行4次操作, 删除I, N, T, N四个元素, 变为#E, 或者我们可以认为从#E变到#INTEN需要最少进行四步操作, 即增加INTN这4个元素,我们不要考虑#E增加了四个元素其后面序列就向后移动4位, 我们假设现在Y序列就只有#E, 没有后面的元素, 我们再来看一下黄框中的元素, 其中3可以看做#E变为#IN需要三步, 删除E, 加I, 加N, 那么此时4代表由#EX变为#IN在#E已经变为#IN的基础上还需要最少几步, 那么就是4步, 多出的一步就是删除#EX中的X, 因为#E已经用3步变为#IN了, 即可以看做现在是#INX变为#IN需要多少步, 那当然只需要多一步了, 当然其实这么来说不准确, 因为4不一定是由3+1得到的, 也可能是4的左下的2经过2+2得到的, 也可能是4下面那个3通过+1得到的。

根据上图, 可以认为下图矩阵中向右移动代表删除, 因为从#E到#EX就是删除了一位元素, 所以此时来考虑添加元素会导致整体后半序列向后移动的问题, 因为我们的目标是得到右上角的值, 所以在这过程中我们可能先向上移动(增加), 再向右移动(删除), 或者斜向右上角走一步(替换), 而我们的子状态可以认为是在上个字符串中所需步数, 即假如Y字符串(底部的字符串)是#EX, 如果要变为#INTEN的话需要4步, 那么如果字符串是#EX呢, 则需要5步, 那如果是#EXE呢, 那么需要6步, 这么一步一步, 每一步可以利用上一步的结论, 直到最后#EXECUTION变为#INTEN需要多少步, 但是我们希望得到右上角的元素, 即#EXECUTION完全变成#INTENTION, 总共需要8步。 不要想得过于复杂要是Y字符串往里边添加元素后边序列又移怎么办, 我们每次子状态只是考虑当前的序列, 而下次序列只是利用当前序列得到的结论, 如果发现多了一位元素的话要删除的话就删除, 这样就不会有多出来的序列了, 这么一来总有一条最佳路径走到右上角的

但是我们希望得到右上角的元素, 即#INTENTION完全变成#EXECUTION, 总共需要8步。

AFAA5B9452E1C3FB85C1EB5715C69319.png

代码实现:

from pprint import pprint
def min_edit(strA,strB):
    grid=[[j for j in range(len(s2)+1)]]+[[j+1 if i==0 else 0 for i in range(len(s2)+1)] for j in range(len(s1))]
    strA,strB='#'+strA,'#'+strB
    for i in range(1,len(grid)):
        for j in range(1,len(grid[0])):
            temp=2 if strA[j]!=strB[i] else 0
            grid[i][j]=min(grid[i-1][j]+1,grid[i][j-1]+1,grid[i-1][j-1]+temp)
    pprint(grid)
    return grid[-1][-1]

min_edit('INTENTION','EXECUTION')

同理, 这道题也能用之前的背包问题类似的简化空间复杂度的方法, 用滚动数组, 即每次迭代下一行的时候只需要把之前的那一行保留下来就行, 因为只需要之前那一行的数据:

def minDistance(word1, word2):
        l1, l2 = len(word1)+1, len(word2)+1
        pre = [0 for _ in range(l2)]
        for j in range(l2):
            pre[j] = j
        for i in range(1, l1):
            cur = [i]*l2
            for j in range(1, l2):
                cur[j] = min(cur[j-1]+1, pre[j]+1, pre[j-1]+2*(word1[i-1]!=word2[j-1]))
            pre = cur[:]
        return pre[-1]

5. 最大面积问题

histogram的最大面积 (Leetcode 84)(单调栈问题)

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

A0D86BE3885FB19D497A74D1A5FA7F5C.jpg

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

281856BE95CC68AAFA6591D388D4A929.jpg

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

这道题可以用动态规划或者分治算法, 如果用动态规划的话如下图

整个流程

代码如下:

def largestRectangleArea(heights):
    stack,max_area=[-1],0
    for i in range(len(heights)):
        #若当前位置中的比stack中最顶上的元素还要小, 那么就将该元素取出, 算当前元素到取出元素所围成的面积大小
        #将得到的结果与max_area比较, 然后再比较当前stack最顶上元素是否大于当前元素, 如果大于的话继续取出来
        #其中stack中存的是下标, 而i-stack[-1]-1算的是围起来的矩阵的宽
        while stack[-1]!=-1 and heights[stack[-1]]>=heights[i]:
            max_area=max(heights[stack.pop()]*(i-stack[-1]-1),max_area)
        stack.append(i)
    #此时是将整个heights列表迭代完后stack中还有值
    while stack[-1]!=-1:
        #注意是用len(height)减去stack[-1]-1而不再是用i减
        max_area=max(heights[stack.pop()]*(len(heights)-stack[-1]-1),max_area)
    return max_area
    
print(largestRectangleArea([6,7,5,2,4,9,5,3]))

矩阵最大面积 (Leetcode 85)

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

该题可用上文中提及的histogram计算方法计算, 即将每一行的每一列都看做一个histogram, 譬如上面Example 中的 Input, 第1行中第二列(下标从0开始算)即 matrix[1][2] 此时的histogram的高度等于2, 即等于matrix[0][2]的 1 加上matrix[1][2]的1, 如果碰到像 matrix[1][1]中的0, 则将当前的从上到下的累积高度清空

def maximalRectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    col,max_area=len(matrix[0]),0
    height=[0 for i in range(col)]
    for i in range(len(matrix)):
        stack=[-1]
        #与之前hist算法不同的仅仅是此处计算了一下在当前行每个列所对应的hist的高度
        for j in range(col):
            height[j]=height[j]+1 if matrix[i][j]=='1' else 0
        for j in range(col):
            while stack[-1]!=-1 and height[j]<height[stack[-1]]:
                max_area=max(max_area,height[stack.pop()]*(j-stack[-1]-1))
            stack.append(j)
        while stack[-1]!=-1:
            max_area=max(max_area,height[stack.pop()]*(col-stack[-1]-1))
    return max_area
    
print(maximalRectangle(
[["1","0","1","1","0","1"],
 ["1","1","1","1","1","1"],
 ["0","1","1","0","1","1"],
 ["1","1","1","0","1","0"],
 ["0","1","1","1","1","1"],
 ["1","1","0","1","1","1"]]
))

除此之外还有另一种想法, 即:

[
   ["1","0","1","0","0"],
   ["1","0","1","1","1"],
   ["1","1","1","1","1"],
   ["1","0","0","1","0"]
 ]

• 策略: 把matrix看成多个直方图, 每一行及其上方的数据都构成一个直方图, 需要考察matrix.size()个直方图
• 对于每个点(row, col), 我们最后都计算以这个点上方的连续的'1'往left, right方向延申可以得到的最大的矩形的面积
• 通过这种方法获取的矩形一定会把最大的矩形包含在内
• height[row][col]记录的是(row, col)这个坐标为底座的直方图柱子的高度, 如果这个点是'0', 那么高度当然是0了
• left[row][col]记录的是(row, col)这个坐标点对应的height可以延申到的最左边的位置
• right[row][col]记录的是(row, col)这个坐标点对应的height可以延申到的最右边的位置+1
• 以上面的matrix为例, 其中index从0开始
• 对于(row=2, col=1)这个点, left=0 (此处left和right指代的是下标, 而不是1的数量), right=5, height=1, 因为height=1, 所以只需要考虑row=2这行
• 对于(row=2, col=2)这个点, left=2, right=3, height=3, 因为height=3, 所以还要考虑(row=1,col=2)和(row=0,col=2)
• (2,2)这个点与(2,1)紧挨着,left和right却已经变化如此之大了, 这是因为left和right除了受左右两边的'1'影响, 还受到了其上方连续的'1'的制约
• 由于点(2,2)上有height=3个'1', 这几个'1'的left的最大值作为当前点的left, 这几个'1'的right的最小值作为当前点的right
• 因此, 实际上, 我们是要找以hight对应的这条线段往左右两边移动(只能往全是'1'的地方移动), 可以扫过的最大面积
• 当hight与目标最大矩形区域的最短的height重合时, 最大矩形的面积就找到了, 如上面的例子, 就是点(2,3)或(2,4)对应的height

6. Paint house类型问题(同时可用分治+递归+记忆法解决的问题)

气球问题 Leetcode

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and rightare adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

• You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
• 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Input: [3,1,5,8]
Output: 167 
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
             coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

**思路过程: **如果采用暴力破解的方式, 复杂度为 n*(n-1)*(n-2)*(n-3)…..复杂度为O(n!), 此时我们需要思考在暴力破解的方式中有哪部分是冗余的, 因此我们想到能不能将列表分成多个部分, 但是分为多个部分, 但是随着气球的爆炸不同部分间会合并到一起, 由于当前情况下所能得到最大程度的coins不依赖于已经爆炸的气球, 所以我们考虑采用memorization方式, 由于每次爆炸所能得到的coin的式子是nums[i-1]*nums[i]*nums[i+1], 而我们此时当只剩一个气球的时候, 此时所能得到的coin是nums[0-1]*nums[i]*nums[n], 注意其中nums的下标是从0到n-1, 所以此处nums[0-1]=nums[-1]和nums[n]取不到值 (此处不是python, -1取不到值), 由题目得又可写成1*nums[i]*1. 那么我们对n个气球中的每一个都计算一次当其为最后一个爆炸的气球的情况。

此时我们在假定 i 为最后一个爆炸的气球后, 最开始的气球队列nums就可以分成两部分, 一个是 i 左边的部分, 一个是 i 右边的部分, 因为 i 是最后一个爆炸的气球, 所以左边部分和右边部分无论如何都合并不了(因为合并了就说明 i 已经爆炸了, 但 i 是最后一个爆炸的) , 也就是说左边和右边部分此时可以独立考虑, 所以此时问题转变为, 左边部分的哪种爆炸顺序能最大化所得coins的值和右边部分哪种爆炸顺序能最大化所得的coins的值

既然能分为左右两独立部分, 此时应该想到带memorization的递归, 即假如现在认为 i 为最后一个爆炸的, 将左部分递归, 此时左部分变为整个输入列表, 再对这个输入列表做迭代, 认为 j 是最后一个爆炸的, 再分为两部分再递归, 以此循环, 就有如下分治算法代码, 注意, 第一次以 i 作为最后爆炸气球时, 是计算 nums[-1]*nums[i]*nums[n] , 而分开后变为左右两个序列后, 假如设定 j 是左序列中最后一个爆的, 那么此时就是 nums[left-1]*nums[j]*nums[right+1], 但实际上 j 相当于倒数第二个或者第三个爆的 (左右两个分部不确定那个先)

def maxCoins(nums):
    #这一步确保了将nums中所有为0的值都去掉, 因为没有意义
    #为了避免出现nums[-1]和nums[length]情况时报错, 所以两边各加一个1
    grid,nums={},[1]+[n for n in nums if n]+[1]
    def helper(i,j):
        if i+1==j: return 0
        if (i,j) not in grid:
            #由于是最后一个爆炸的气球, 所以需要用nums[left-1]*nums[k]*nums[right+1]
            #当输入整个序列时, left=0, right=len(nums)-1, 所以会产生nums[-1]*nums[k]*nums[n]
            grid[i,j]=max(helper(i,k)+nums[i]*nums[k]*nums[j]+helper(k,j) for k in range(i+1,j))
        return grid[i,j]
    return helper(0,len(nums)-1)
print(maxCoins([3,1,5,8]))

如果采用动态规划的话, 过程如下, 其中 i 和 j 中间的间隔是当选这个间隔内的某一个气球k最后一个爆炸时, 该间隔所能得到coins的最大值, 即:

max_value=0

for k in ( i~j ):

coin=if k burst last

max_value=max(coin, max_value)

然而要求出coin=if k burst last, 还需要一个迭代, 就是迭代上面递归中提到的通项公式, 即:

grid[leftmost][rightmost]=max(grid[left][right],nums[leftmost-1]*nums[k]*nums[rightmost+1]+grid[leftmost][k-1]+grid[k+1][rightmost])

其中 i 和 j 可以认为是上式中的leftmost和rightmost, 因为较为清晰所以用leftmost和rightmost代替, 其中grid[left][most]指代的在leftmost和rightmost区间内所能得到最大的coin值, 很显然, 最后要求的是 (i=0, j=length) 区域内最大coins数量

流程-1

流程-2

以 [3,1,5,8]举例子, 整个grid矩阵更新过程是:

0    0    0    0    0    0
0    3    0    0    0    0
0    0    15   0    0    0
0    0    0    40   0    0
0    0    0    0    40   0
0    0    0    0    0    0

然后

0    0    0    0    0    0
0    3    30   0    0    0
0    0    15   135  0    0
0    0    0    40   48   0
0    0    0    0    40   0
0    0    0    0    0    0

最终

0    0    0    0    0    0
0    3    30   159  167  0
0    0    15   135  159  0
0    0    0    40   48   0
0    0    0    0    40   0
0    0    0    0    0    0

def maxCoins(nums):
    nums=[1]+[n for n in nums if n]+[1]
    length=len(nums)-2
    grid=[[0]*len(nums) for i in range(len(nums))]
    #注意此处是先j后i
    for j in range(1,length+1):
        for i in range(j,0,-1):
        #截止到此处, 上面两个循环是确保从左到右, 从底向上将dp矩阵每个值更新
            for k in range(i,j+1):
                #此处就是上面递归方法中的通项公式
                #其中grid[i][j]等于在left~right区间中, 根据其中每一个值将列表分为两半时, 得到的最大值
                grid[i][j]=max(grid[i][j],nums[i-1]*nums[k]*nums[j+1]+grid[i][k-1]+grid[k+1][j])
    return grid[1][length]

单词拼接问题 Leetcode 139

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

如果采用带memorization的递归问题的话, 如下:

def wordBreak(s, wordDict):
    memo=[None]*len(s)
    def helper(start):
        if start==len(s):
            return True
        if memo[start]!=None:
            return memo[start]
        for end in range(start+1,len(s)+1):
            if s[start:end] in wordDict and helper(end):
                memo[start]=True
                return memo[start]
        memo[start]=False
        print(memo)
        return memo[start]
    #注意此处return的相当是memo[0]而不是memo[-1]
    return helper(0)

print(wordBreak("aaaab",["a","aa","aaa","aaaa"]))

上例中, 每一轮print出的memo是:

[None, None, None, None, False]
[None, None, None, False, False]
[None, None, False, False, False]
[None, False, False, False, False]
[False, False, False, False, False]

由此可见, 联想递归过程, 假如第一轮选中了wordDict[3]=’aaaa’, 走到了s[4]这个位置, 然后在s[:4]=‘aaaa’的基础上, 发现遍历wordDict中所有元素, 都无法找到’b’, 那么就说明, s[4]这个位置是行不通的, 此时memo[4]=False, 所以如果通过wordDict[0]+wordDict[2]=‘a’+’aaa’到达了s[4]这个位置, 直接查阅memo[4]发现是False, 那么就没有必要又在该位置重新迭代一遍word[Dict]了。

将递归拆成循环, 就有了下边的动态规划解法:

def wordBreak(s,wordDict):
    length=len(s)
    memo=[None]*length+[True]
    for i in range(length-1,-1,-1):
        for j in range(i+1,length+1):
            if s[i:j] in wordDict and memo[j]!=False:
                memo[i]=True
                break
        memo[i]=True if memo[i] else False
    return memo[0]

7. 动态规划与树结合

Unique二叉搜索树问题(Leetcode 96)

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation: Given *n* = 3, there are a total of 5 unique BST's:

当input为3时所有可能的树

注意此处是二叉搜索树, 中序遍历会产生从小到大的序列。

/*
在这个问题中, 我们思考两个问题:

1)我们要遍历每一个可能的根节点, 假如输入是5的话, 我们需要遍历 1,2,3,4,5 分别将其作为根节点。 因为数列是有序的, 那么当某个数被作为根节点时, 整个数列会被其分开为左右两部分, 我们现在假设G(i)代表当数列被以i为中心分为两半时, 所能得到unique BST的数量。假设 1,2,3,4,5 被3从中间分开, 那么 左边就是 1,2 右边就是 4,5。很显然, 左右两边是完全独立的, 也就是说, G(3)的值为 左树的所有排列组合*右树的所有排列组合。也就是相当于左树和右树的笛卡尔积。

2)我们接着来思考第二个问题, 此时左树为1,2右树为4,5 。那么此时左树的所有可能的排列组合的数目是不是等于右树的。那么也就是说, 排列组合的数目跟数字的具体内容无关, 而跟数字的数量有关。假如我们现在用两个数组成一个二叉搜索树, 那么无论这两个点是(1,2)或是(4,5)还是(8,9)。  其可能的排列组合结果数量都是2。也就是说G(2)=2。

3) 那如果现在是三个点的一个数列呢, 譬如[1,2,3], 那G(3)等于多少? 
    我们首先将1作为根节点, 此时左树为[], 右树为[2,3]; 那么此时的值为 G(0)*G(2)
    接着我们将2作为根节点, 此时左树为[1], 右树为[3]; 那么此时的值为 G(1)*G(1)
    最后我们将3作为根节点, 此时左树为[1,2], 右树为[]; 那么此时的值为 G(2)*G(0)
    
    那么最后 G(3)=G(0)*G(2)+G(1)*G(1)+G(2)*G(0)

那么此时就很明了了, 我们只需要将状态累积下来, 每一轮做累加即可。下面代码中的grid就相当于是G

*/
int numTrees(int n) {
        vector<int> grid(n+1);  //因为我们要取到n本身, 所以如果从下标0开始的话需要一共取n+1个数
        grid[0]=grid[1]=1;
        for(int right_bound=2;right_bound<=n;right_bound++){  //grid[0]和grid[1]都已经给出, 可以直接从2开始
            for(int cur_root=1;cur_root<=right_bound;cur_root++){
                grid[right_bound]+=grid[cur_root-1]*grid[right_bound-cur_root]; //就是上面提到的累积product
            }
        }
        return grid[n];
    }