和分治法一樣，動態(tài)規(guī)劃（dynamic programming）是通過組合子問題而解決整個問題的解。

分治法是將問題劃分成一些獨立的子問題，遞歸地求解各子問題，然后合并子問題的解。

動態(tài)規(guī)劃適用于子問題不是獨立的情況，也就是各子問題包含公共的子子問題。

此時，分治法會做許多不必要的工作，即重復(fù)地求解公共的子問題。動態(tài)規(guī)劃算法對每個子問題只求解一次，將其結(jié)果保存起來，從而避免每次遇到各個子問題時重新計算答案。

適用范圍

最優(yōu)性原理體現(xiàn)為問題的最優(yōu)子結(jié)構(gòu)特性。當(dāng)一個問題的最優(yōu)解中包含了子問題的最優(yōu)解時，則稱該問題具有最優(yōu)子結(jié)構(gòu)特性。

最優(yōu)性原理是動態(tài)規(guī)劃的基礎(chǔ)。任何一個問題，如果失去了這個最優(yōu)性原理的支持，就不可能用動態(tài)規(guī)劃設(shè)計求解。

1.問題中的狀態(tài)滿足最優(yōu)性原理。

2.問題中的狀態(tài)必須滿足無后效性。

所謂無后效性是指：“下一時刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無關(guān)，當(dāng)前狀態(tài)是對以往決策的總結(jié)”。

動態(tài)規(guī)劃算法的設(shè)計

兩種方法：

自頂向下（又稱記憶化搜索、備忘錄）：基本上對應(yīng)著遞歸函數(shù)實現(xiàn)，從大范圍開始計算，要注意不斷保存中間結(jié)果，避免重復(fù)計算

自底向上（遞推）：從小范圍遞推計算到大范圍

遞歸方程+邊界條件

動態(tài)規(guī)劃問題匯總

1. 子序列問題

爬樓梯問題 (leetcode 70題)

一個人每次只能走一層樓梯或者兩層樓梯，問走到第80層樓梯一共有多少種方法。

到第n步有兩個選擇

從第n-2步一次跨兩步到第n個位置

或者從第n-1步跨一步到第n個位置

(不要考慮從第n-2跨一步到n-1再跨一步到n, 因為那也算是經(jīng)過n-1)

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

然而第n-2步也可以由第n-4和第n-3兩種走法, 以此類推直到第n=2步時

設(shè)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)

除此之外, 還可以用遞歸算法

而且其符合斐波那契數(shù)列的定義:

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

故用程序?qū)懙脑捑褪?

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個數(shù):

最長上升子序列

最長上升子序列就符合這一特性。我們要求n個數(shù)的最長上升子序列，可以求前n-1個數(shù)的最長上升子序列，再跟第n個數(shù)進(jìn)行判斷。求前n-1個數(shù)的最長上升子序列，可以通過求前n-2個數(shù)的最長上升子序列……直到求前1個數(shù)的最長上升子序列，此時LIS當(dāng)然為1。

讓我們舉個例子：求 2 7 1 5 6 4 3 8 9 的最長上升子序列。我們定義d(i) (i∈[1,n])來表示前i個數(shù)以A[i]結(jié)尾的最長上升子序列長度。

前1個數(shù) d(1)=1 子序列為2；

前2個數(shù) 7前面有2小于7 d(2)=d(1)+1=2 子序列為2 7

前3個數(shù) 在1前面沒有比1更小的，1自身組成長度為1的子序列 d(3)=1 子序列為1

前4個數(shù) 5前面有2小于5 d(4)=d(1)+1=2 子序列為2 5

前5個數(shù) 6前面有2 5小于6 d(5)=d(4)+1=3 子序列為2 5 6

前6個數(shù) 4前面有2小于4 d(6)=d(1)+1=2 子序列為2 4

前7個數(shù) 3前面有2小于3 d(3)=d(1)+1=2 子序列為2 3

前8個數(shù) 8前面有2 5 6小于8 d(8)=d(5)+1=4 子序列為2 5 6 8

前9個數(shù) 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個數(shù)的LIS為d(9)=5

所以我們的程序就從第一個元素開始, 首先第一個元素的長度為1, 然后第二個元素比第一個元素大, 所以第二個元素的長度等于第一個的長度加1, 第三個比前兩個都小, 長度為1,第四個比第三個和第一個元素都要大, 所以找出第三個和第一個元素所對應(yīng)長度中較大的那個然后加1作為第四個元素的長度, 以此類推

#一看到這題, 首先應(yīng)該想到帶memorization的方法, 一步一步查前一步的memo中的對應(yīng)元素就行
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:
            #此處是防止當(dāng)前值前沒有任何值小于當(dāng)前值, 會出現(xiàn)max的數(shù)組是空的報錯
            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。

這道題應(yīng)該首先想到two pointer的解法, 接著想到可以用memorization記錄之前的公共子序列長度, 因為是two pointer, 所以建立二維memo矩陣

假設(shè)兩個序列數(shù)組分別為a，b。定義f(i,j)為計算到a數(shù)組第i個數(shù)、b數(shù)組第j個數(shù)時所得到的最長公共子序列的長度。這時有兩種情況：

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)

設(shè) X=(x1,x2,.....xn) 和 Y={y1,y2,.....ym} 是兩個序列

1）如果 xn=ym

**即X的最后一個元素與Y的最后一個元素相同，這說明該元素一定位于公共子序列中。因此，現(xiàn)在只需要找：LCS(Xn-1，Ym-1)
**

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

****它產(chǎn)生了兩個子問題：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.當(dāng)i或j等于0，MaxLen(i,j)==0;  2 當(dāng)s1和s2的最后一個字符相同時，MaxLen(i,j)=MaxLen(i-1,j-1)+1;  3 當(dāng)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.

/*
這個問題最麻煩的就是, 需要考慮負(fù)數(shù), 即加入輸入序列是[-2,1,-3], 那么最終答案是6, 如果沒有負(fù)數(shù)的話, 遞推公式只需要 grid[i]=max(grid[i-1]*nums[i],nums[i]) 即可, 即用遞推公式?jīng)Q定是否繼續(xù)之前的累積下去, 還是從現(xiàn)在開始重新開始新一輪的累積, 因為這個遞推公式是從0開始的, 所以可以認(rèn)定每一輪都能選擇到最優(yōu)的累積方式。

首先我們開始nums[0], grid[0]=nums[0]; 然后grid[1]=max(grid[0]*nums[1],nums[1]), 在這一步中g(shù)rid[1]的最后選出來的結(jié)果肯定是最優(yōu)的; 接著grid[2]=max(grid[0]*nums[1],nums[1]), 因為grid[1]是最優(yōu)的, 所以這么選出來的grid[2]肯定也是最優(yōu)的, 注意, 我們在思考grid[2]的時候 不需要 又想grid[1]是否是最優(yōu)的呢, 因為我們一步一步迭代過來的, grid[1]肯定是最優(yōu)的, 所以我們在思考grid[2]的時候就假定grid[1]已經(jīng)是最優(yōu)的了。

在上面這個過程中, 我們發(fā)現(xiàn)其實grid這個矩陣可有可無, 我們在第i輪只需要知道grid[i-1]的大小, 而不需要考慮grid[i-2],grid[i-3]...之類的, 那么我們可以專門拿出一個變量就存上一輪的grid[i-1], 因此連grid矩陣都不需要了

可是, 上述討論的這些內(nèi)容, 僅僅是在序列中所有數(shù)都為正的情況下, 如果是包括負(fù)數(shù), 因為有負(fù)負(fù)得正的情況, 所以像[-2,1,-3]這種情況, 按照上面的方法就錯了, 因為在第二輪的時候就會把-2扔了, 將1保留下來作為當(dāng)前輪的狀態(tài)。

那么我們知道負(fù)數(shù)是小于0的, 而正數(shù)是大于0的, 所以我們在保存上一輪的狀態(tài)時, 保留兩個值, 一個是上一輪狀態(tài)的最小值, 一個是最大值, 因為如果有負(fù)數(shù)出現(xiàn)的話上一輪狀態(tài)最小值肯定是負(fù)數(shù)。然后上一輪最小狀態(tài)和最大狀態(tài)之間交叉求值。 

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

第一輪, 2為當(dāng)前循環(huán)值, past_min=2, past_max=2
第二輪, -1為當(dāng)前循環(huán)值, past_min=-2, past_max=-1
第三輪, 3為當(dāng)前循環(huán)值, past_min=-6, past_max=3
第四輪, -5為當(dāng)前循環(huán)值, past_min=past_max*-5=-15, past_max=past_min*-5=30      //進(jìn)行了一次交叉, 因為碰到了負(fù)負(fù)得正的情況, past_min和past_max互換
第五輪, 4為當(dāng)前循環(huán)值, 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())能確保可以解決負(fù)負(fù)得正的情況
            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())能確?？梢越鉀Q負(fù)負(fù)得正的情況
            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位置上元素結(jié)束的最長有效substring, 我們需要想明白這幾點:

• [1] 如果第i位置上是‘(’的話那么一定dp[i]=0, 因為不會有以‘(’結(jié)尾的有效字符串

• [2] 根據(jù)上條原則, 僅當(dāng)i位置上的字符為‘)’時dp[i]才有可能不為0

• [3] 對于最終Output大于等于2的字符串, 其中一定有兩個相鄰的字符分別為‘(’和‘)’, 即‘()’一定在字符串的某一處出現(xiàn)了

• [4] 思考這樣一個例子: ‘( ( ( ) ) )’, 我們希望的是首先找到最里邊的‘()’, 接著再向外面擴(kuò)一層, 變?yōu)?‘( ( ) )’, 以此類推

• [5] 對于復(fù)雜一些的例子譬如 ‘( ( ) ( ) )’, 假設(shè)這6個字符的下標(biāo)分別為0到5, 假設(shè)該字符串用S表示, 首先我們先找到 S[1:3]=‘()’, 故dp[2]=2, 以此類推, 我么發(fā)現(xiàn)S[3:5]=‘()’, 此時我們希望dp[4]=4而不是2, 因為前面已經(jīng)有一個相連的有效的字符串了即S[1:3], 那么此時我們可以認(rèn)為dp[4]=dp[2]+2, 再來看最后一位S[5], 我們希望其能與S[0]匹配上, 那么此時我們希望跳過中間這4個, 我們發(fā)現(xiàn)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]=‘(’時, 此時字符串看上去是: ……(), 那么此時有(根據(jù)上述第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的判斷會導(dǎo)致i-dp[i-1]-2=-1的情況發(fā)生, 但是其實沒關(guān)系, 因為dp的值是從前往后賦的, 而dp初始化為0, 所以dp[-1]==0
                #不過如果將大于等于改為大于的話, 會導(dǎo)致當(dāng)i-dp[i-1]-1==0時不進(jìn)入if循環(huán), 此時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方法) :

• 首先發(fā)現(xiàn)第一個’()’, 然后向外擴(kuò)展

• 每成功擴(kuò)展一次(也就意味著當(dāng)前連著的substring長度加上已經(jīng)被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]當(dāng)做上邊那種寫法的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 簡介

來自http://www.itdecent.cn/p/25f4a183ede5

假設(shè)我們有n件物品，分別編號為1, 2...n。其中編號為i的物品價值為vi，它的重量為wi。為了簡化問題，假定價值和重量都是整數(shù)值?，F(xiàn)在，假設(shè)我們有一個背包，它能夠承載的重量是W?，F(xiàn)在，我們希望往包里裝這些物品，使得包里裝的物品價值最大化，那么我們該如何來選擇裝的東西呢？問題結(jié)構(gòu)如下圖所示：

9960E20BF17B1BF2735BB0086C9AD6CB.png

這個問題其實根據(jù)不同的情況可以歸結(jié)為不同的解決方法。假定我們這里選取的物品每個都是獨立的，不能選取部分。也就是說我們要么選取某個物品，要么不能選取，不能只選取一個物品的一部分。這種情況，我們稱之為0-1背包問題。而如果我們可以使用部分的物品的話，這個問題則成為部分背包(fractional knapsack)問題。這里我們只考慮0-1背包問題。

3.2 初步分析

對于這個問題，一開始確實有點不太好入手。一堆的物品，每一個都有一定的質(zhì)量和價值，我們能夠裝入的總重量有限制，該怎么來裝使得價值最大呢？對于這n個物品，每個物品我們可能會選，也可能不選，那么我們總共就可能有2^n種組合選擇方式。如果我們采用這種辦法來硬算的話，則整體的時間復(fù)雜度就達(dá)到指數(shù)級別的，肯定不可行。

現(xiàn)在我們換一種思路。既然每一種物品都有價格和重量，我們優(yōu)先挑選那些單位價格最高的是否可行呢？比如在下圖中，我們有3種物品，他們的重量和價格分別是10, 20, 30 kg和60, 100, 120。

0D5F1307CC777CEFDAD3C4EC6360C28D.png

那么按照單位價格來算的話，我們最先應(yīng)該挑選的是價格為60的元素，選擇它之后，背包還剩下50 - 10 = 40kg。再繼續(xù)前面的選擇，我們應(yīng)該挑選價格為100的元素，這樣背包里的總價值為60 + 100 = 160。所占用的重量為30, 剩下20kg。因為后面需要挑選的物品為30kg已經(jīng)超出背包的容量了。我們按照這種思路能選擇到的最多就是前面兩個物品。如下圖：

549CAF213ADCC06513E38168B3FE7A88.png

按照我們前面的期望，這樣選擇得到的價值應(yīng)該是最大的。可是由于有一個背包重量的限制，這里只用了30kg，還有剩下20kg浪費了。這會是最優(yōu)的選擇嗎？我們看看所有的選擇情況：

D1496B280FE34EF6EA0CBACE88652AC9.png

很遺憾，在這幾種選擇情況中，我們前面的選擇反而是帶來價值最低的。而選擇重量分別為20kg和30kg的物品帶來了最大的價值?？磥?，我們剛才這種選擇最佳單位價格的方式也行不通。

3.3 動態(tài)規(guī)劃思路

既然前面兩種辦法都不可行，我們再來看看有沒有別的方法。我們再來看這個問題。假設(shè)我們已經(jīng)選擇n個元素中的若干個來形成最優(yōu)解，假定為k個。那么對于這k個元素a1, a2, ...ak來說，它們組成的物品組合必然滿足總重量<=背包重量限制，而且它們的價值必然是最大的。因為它們是我們假定的最優(yōu)選擇，肯定價值應(yīng)該是最大的。假定ak是在構(gòu)造這個最優(yōu)選擇期間我們按照順序放入的最后一個物品。它的重量為wk，它的價值為vk。既然我們前面選擇的這k個元素構(gòu)成了最優(yōu)選擇，如果我們把這個ak物品拿走，對應(yīng)于k-1個物品來說，它們所涵蓋的重量范圍為0~(W-wk)。假定W為背包允許承重的量。假定最終的價值是V，剩下的物品所構(gòu)成的價值為V-vk。這剩下的k-1個元素是不是構(gòu)成了一個這種W-wk的最優(yōu)解呢？

我們可以用反證法來推導(dǎo)。假定拿走ak這個物品后，剩下的這些物品沒有構(gòu)成W-wk重量范圍的最佳價值選擇。那么我們肯定有另外k-1個元素，他們在W-wk重量范圍內(nèi)構(gòu)成的價值更大。如果這樣的話，我們用這k-1個物品再加上第k個，(注意此處的重量限制是小于W-wk, 也就是說剩下的k-1個元素?zé)o論怎么構(gòu)建, 只要滿足重量限制在W-wk之內(nèi), 肯定最終是放得ak的) 他們構(gòu)成的最終W重量范圍內(nèi)的價值就是最優(yōu)的。這豈不是和我們前面假設(shè)的k個元素構(gòu)成最佳矛盾了嗎？所以我們可以肯定，在這k個元素里拿掉最后那個元素，前面剩下的元素依然構(gòu)成一個最佳解。

現(xiàn)在我們經(jīng)過前面的推理已經(jīng)得到了一個基本的遞推關(guān)系，就是一個最優(yōu)解的子解集也是最優(yōu)的。可是，我們該怎么來求得這個最優(yōu)解呢？我們這樣來看。假定我們定義一個函數(shù)c[i, w]表示到第i個元素為止，在限制總重量為w的情況下我們所能選擇到的最優(yōu)解。那么這個最優(yōu)解要么包含有i這個物品，要么不包含，肯定是這兩種情況中的一種。如果我們選擇了第i個物品，那么實際上這個最優(yōu)解是c[i - 1, w-wi] + vi (即前i-1個物品需要是滿足w-wi重量的限制, 其中wi是當(dāng)前這第i個物品的重量)。而如果我們沒有選擇第i個物品，這個最優(yōu)解是c[i-1, w] (即前i-1個物品滿足小于w的重量限制就可以了, 因為沒有加第i個物品, 所以重量限制是w)。這樣，實際上對于到底要不要取第i個物品，我們只要比較這兩種情況，哪個的結(jié)果值更大不就是最優(yōu)的么？

在前面討論的關(guān)系里，還有一個情況我們需要考慮的就是，我們這個最優(yōu)解是基于選擇物品i時總重量還是在w范圍內(nèi)的，如果超出了呢？我們肯定不能選擇它，這就和c[i-1, w]一樣。

這里有一點值得注意，這里的wi指的是第i個物品的重量，而不是到第i個物品時的總重量。

另外，對于初始的情況呢？很明顯c[0, w]里不管w是多少，肯定為0。因為它表示我們一個物品都不選擇的情況。c[i, 0]也一樣，當(dāng)我們總重量限制為0時，肯定價值為0。

這樣，基于我們前面討論的這3個部分，我們可以得到一個如下的遞推公式：

672E5F939DE183A29CDBD9675689F86C.png

有了這個關(guān)系，我們可以更進(jìn)一步的來考慮代碼實現(xiàn)了。我們有這么一個遞歸的關(guān)系，其中，后面的函數(shù)結(jié)果其實是依賴于前面的結(jié)果的。我們只要按照前面求出來最基礎(chǔ)的最優(yōu)條件，然后往后面一步步遞推，就可以找到結(jié)果了。

我們再來考慮一下具體實現(xiàn)的細(xì)節(jié)。這一組物品分別有價值和重量，我們可以定義兩個數(shù)組int[] v, int[] w。v[i]表示第i個物品的價值，w[i]表示第i個物品的重量。為了表示c[i, w]，我們可以使用一個int[i][w]的矩陣。其中i為物品的數(shù)量，而w表示最大的重量限制。按照前面的遞推關(guān)系，c[i][0]和c[0][w]都是0。而我們所要求的最終結(jié)果是c[n][w]。所以我們實際中創(chuàng)建的矩陣是(n + 1) x (w + 1)的規(guī)格。

假設(shè)有5件物品，其重量分別是w={2，2，6，5，4}，價值分別是v={6，3，5，4，6}，背包容量為10。其C[i,w]矩陣顯示如下(其中綠色的列代表當(dāng)前限制重量, 即當(dāng)限制重量為1,2,3,4,5,6,7,8,9,10時, 每一行代表當(dāng)最大所能包含的物品數(shù)量分別為1,2,3,4,5時, 其在不同限制重量下最優(yōu)解的價值):

3E20509209642CF33412E9F3936B1FBC.png

注意上圖, 在沒添加進(jìn)物品4的時候, 只有物品123的時候, 在最大限重為6的情況下, 最高的價值為9, 在允許使用物品4后, 此時在限重6的情況下最大價值為12 (即物品4+物品0)

3.4 Python代碼實現(xiàn)

下面代碼實現(xiàn)了上圖中的矩陣:

import pprint
def package(max_weight,weight_list,value_list):
    #這里橫行的數(shù)量加一是為了確保之后每次grid[cur_item_index-1][cur_weight_limit]中的減一不會出現(xiàn)0-1=-1的情況
    #這里縱行的數(shù)量加一是因為要取到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 復(fù)雜度優(yōu)化

以上方法的時間和空間復(fù)雜度均為 O(N*W)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu) 化了，但空間復(fù)雜度卻可以優(yōu)化到 O(W)。
先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán) i=1..N，每次算出來 二維數(shù)組 f[i][0..W]的所有值。那么，如果只用一個數(shù)組 f[0..W]，能不能保證 第 i 次循環(huán)結(jié)束后 f[w]中表示的就是我們定義的狀態(tài) f[i][w]呢?f[i][w]是由 f[i-1][w]和 f[i-1][w-c[i]]兩個子問題遞推而來，能否保證在推 f[i][w]時(也 即在第 i 次主循環(huán)中推 f[w]時)能夠得到 f[i-1][w]和 f[i-1][w-w[i]]的值呢? 事實上，這要求在每次主循環(huán)中我們以 v=V..0 的順序推 f[w]，這樣才能保證推 f[v]時 f[v-w[i]]保存的是狀態(tài) f[i-1][w-w[i]]的值。改進(jìn)后的代碼如下：

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]的信息了
        #因為是從右往左, 每一次循環(huán)在j左邊的元素其實都是上一輪即grid[i-1][:j]的元素, 起到了之前二維矩陣的效果
        #如果是從左往右, 那么每次grid[i][j]更新的值不是依靠grid[i-1][:j], 而是依靠grid[i][:j]了, 所以相當(dāng)于重復(fù)更新了兩邊
        #之所以產(chǎn)生這個原因是因為j-wlist[i], 因為是減號, 所以要調(diào)用左邊的元素, 那么從左往右更新的話, 右邊的元素調(diào)用到的左邊的元素都是更新過的
        #反之從右往左更新的話調(diào)用的元素都是上一輪更新的, 即這一輪還沒更新過
        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 進(jìn)一步思考

我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法。有的題 目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。 一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了 f[0]為 0 其它 f[1..W]均設(shè)為-∞，這樣就可以保證最終得到的 f[N]是一種恰好裝滿背包的最 優(yōu)解。
如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應(yīng)該將 f[0..W]全部設(shè)為 0。
為什么呢?可以這樣理解:初始化的 f 數(shù)組事實上就是在沒有任何物品可以放入 背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為 0 的背包可能 被價值為 0 的 nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未 定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何 容量的背包都有一個合法解“什么都不裝”，這個解的價值為 0，所以初始時狀 態(tài)的值也就全部為 0 了。
這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進(jìn)行狀態(tài)轉(zhuǎn)移 之前的初始化進(jìn)行講解。

3.7 擴(kuò)展: 完全背包問題

完全背包問題與01背包問題的唯一差別就是完全背包問題允許每個物品無限次出現(xiàn), 即每個物品有無限個數(shù)量, 那么其中一種想法就是擴(kuò)展物品集, 假如一個物品的重量為w[i], 而限制的重量為W, 那么這個背包最多只能放下k=W/w[i]件該物品, 所以備選物品中只要有k個物品i就行了, 以此類推, 將備選物品集擴(kuò)展, 然后再用01背包算法, 但是這樣一來01背包算法的grid矩陣就會變得很大, 那么此時我們考慮改一下遞推公式, 變?yōu)?

原來的公式中, 是, 而現(xiàn)在的是, 之前是按每次判斷前i-1個元素中假如當(dāng)前第i個元素和不加入當(dāng)前第i個元素的最優(yōu)解, 因為現(xiàn)在不是i-1了, 對于每一行而言, 這樣一來整個grid矩陣形成的過程中每一個元素生成的過程可以調(diào)用該行前面的元素, 這樣就代表元素可以反復(fù)使用, 而該行被調(diào)用的改行前面的元素又是之前調(diào)用的前面的前面的元素, 以此類推, 直到改行第一個非0元素, 這個非0元素判斷的是加入第i個元素和不加入時前i-1個元素, 在相同的限重范圍內(nèi), 哪個價值比較大

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]))

除此之外, 按照上面改進(jìn)的方法, 還有一種更巧妙的解法, 簡化了空間復(fù)雜度, 即:

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相比唯一的區(qū)別就是solve2是倒序, 這個是正序
        #之前提到了, 從左往右更新每次更新都調(diào)用了之前已經(jīng)更新過的, 這種調(diào)用就是確保了可以復(fù)用元素
        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

下面動圖的邏輯如下:

• 首先根據(jù)最底下那串字符串, 底下字符串每向右移動一次選中一個字符C, grid中就向右移動一格變?yōu)間rid[i][j]
• 如果這格中對應(yīng)的上面的字符 stringUP[j]=C 或者等于左邊的字符 stringLeft[i]中的任意一個的話(三者相等也是一樣的) , 那么判斷下一個條件, 如果不等于那這格的值肯定是False
• 上一條中如果等于其中一個的話, 則判斷grid[i-1][j]和grid[i][j-1]的值, 如果上面的字符 stringUP[j]=C且grid[1][j-1]=True的話, 注意, 此處是當(dāng)grid[i][j]=stringUp[j], 此時判斷左邊那位即grid[i][j-1]是否為True, 同理, 如果grid[i][j]=stringLeft[j]的話, 判斷上一行的grid[i-1][j]是否為True, 如果滿足的話, 那么此時格子的值就為True


39258A8831C9C63C32132D5E58F40CD1.jpg

左邊那列代表當(dāng)前用掉的值, 如果

我們來看下面這張圖片, 在當(dāng)前點grid[i-1][j]和grid[i][j-1]都是True，那代表什么意思呢:

• 我們先看它上面那個即grid[i-1][j], grid[i-1][j]左側(cè)對應(yīng)著a, 而其前面還有一個a, 此時代表當(dāng)前由s1和s2組成的string的前兩個為aa, 然后再看grid[i-1][j]上面對應(yīng)的是b, b前面還有一個d, 那么意思即aa后面接的是db, 所以當(dāng)前情況下, 由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, 然后光標(biāo)再向下移一個, 移到了grid[i][j-1]的位置, 此處再從左邊列表取出一個b, 此時形成了aadb, 那么此時這一行的b已經(jīng)用過了, 光標(biāo)只能向右移了, 所以到了grid[i][j], 即從上面那列再取一個b, 形成了aabdb, 符合最底下字符串的當(dāng)前值
• 也就是說, 如果要到達(dá)grid[i][j]這個元素, 我們可以從其上面grid[i-1][j]為T的對應(yīng)的序列aadb中加入一個從左邊序列抽取出來的b, 或者從其左邊grid[i][j-1]為T所對應(yīng)的序列aadb中加入從上面序列抽取出來的b, 這是為了避免反復(fù)抽取, 譬如(其中L代表從左邊序列抽取出來的, U代表從右邊): a(L)a(L)d(U)b(L), 此時到達(dá)了grid[i][j], 但此時左邊序列的b已經(jīng)被抽取出去構(gòu)成aadb了, 不能再從左邊序列抽取b了, 所以要從上面序列抽取b, 所以要判斷grid[i-1][j]=True并且StringUp(j)=b; 同理, a(L)a(L)d(U)b(U)到達(dá)grid[i][j]后就要判斷左邊序列的情況

6B4A70DA6729CABB100C6E5EDB15BAB4.png

代碼如下:

#O(n)空間復(fù)雜度
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開始計數(shù), 為了能把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)

兩個參考網(wǎng)站: 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中的輸入和輸出

在求解動態(tài)規(guī)劃問題的時候，都需要回答以下幾個問題:

• 狀態(tài)是什么? 在最小編輯距離中，我們定義D[i][j]為長度為i的字符串X和長度為j的字符串Y的最小編輯距離，我們要求解的就是最終的狀態(tài)D[m][n]
• 初始狀態(tài)值是多少?有了狀態(tài)的定義，我們就可以找出初始狀態(tài)的值，因為在動態(tài)規(guī)劃中，我們要做的是求解最終的狀態(tài)， 這必須依賴于初始狀態(tài)和轉(zhuǎn)移方程。一般來說，初始狀態(tài)都是邊界值，就是D[i][0]和D[0][j]。在最小編輯距離問題中，D[i][0]表示長度為i的字符串和長度為0的字符串的最小編輯距離，顯然只能通過刪除操作，得到長度為0的字符串，所以有D[i][0]=i。同理D[0][j]=j
• 轉(zhuǎn)移方程?轉(zhuǎn)移方程是動態(tài)規(guī)劃中的重點，這個方程應(yīng)具體問題具體分析，在本問題中，看下面示意圖:

72521E01A13E04174EC598E05BCCC45E.png

這里我用 # I N T E N T I O N 表示字符串X，# E X E C U T I O N表示字符串Y。假設(shè)現(xiàn)在要計算的是D[i][j]，此時i指向T,j指向E，我們要定義轉(zhuǎn)移方程，也就是如何用已知的狀態(tài)來推出現(xiàn)在的狀態(tài)，換句話說，就是將當(dāng)前狀態(tài)D[i][j]用之前狀態(tài)來求解。

此時我們只看字符串X和字符串Y的前4位元素, 即#INT和#EXE, 不要考慮之后的字符, 在如下討論中分別敘述了紅色, 黃色以及藍(lán)色三種不同的方法

那么怎么表示呢？雖然這個方程需要具體問題具體分析得到，但是分析的過程一般是一樣的，如何做分析呢？

1. 數(shù)型結(jié)合，可以先畫出示意圖，方便我們分析，如上面我畫的這個示意圖；
2. 轉(zhuǎn)化化歸，要知道，我們是想通過用已知來表示未知，所以在示意圖畫出來后，我們要明白要做的是將未知的D[i][j]轉(zhuǎn)化為前面已知狀態(tài)表示。
3. 分類整合,這里實際上有兩個小步驟:

• 分類:用已知表示未知，或者從已知走向未知，路徑往往不唯一！可以說在動態(tài)規(guī)劃問題里肯定是不唯一的，也就是說D[i][j]可以有多條路徑得到。這時候我們就要分類討論，在這個問題中，我在示意圖畫出了三種顏色的線，分別表示三種不同的路徑:

  • 紅色: D[i][j]可以這樣得到，先將X(1..i)轉(zhuǎn)化為Y(1...j-1), 即相當(dāng)于在前一個狀態(tài)中Y(1…j-1)中插入一個Y(j),不要考慮插入Y(j)后面序列會往后移一位的事, 那是之后的步驟考慮的 , 此時應(yīng)該求他們的最小編輯距離D[i][j-1]，然后呢插入Y(j)，所以，最后總的編輯距離為D[i][j] = D[i][j-1] + (insert)

  • 藍(lán)色: D[i][j]可以這樣得到，先將X(1..i-1)轉(zhuǎn)化為Y(1…j)，此時應(yīng)該求他們的最小編輯距離D[i-1][j]，刪除X(i)，所以，最后總的編輯距離為D[i][j] = D[i-1][j] + 1 (delete)

  • 黃色: D[i][j]可以這樣得到，先將長度為i-1的字符串轉(zhuǎn)化為長度為j-1的字符串，此時應(yīng)該求他們的最小編輯距離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

• 整合: 這一步就是對上述所有路徑求最小值(或者最大值)

所以最后的轉(zhuǎn)移方程如下:

F46DBD4046C3E9519337B82DAAB2BDAB.png

因此, 得到的dp圖如下:

3FE991955639A3D1ACE9FB3308B821FC.png

9415DEDCEED26423FB5DC19957B85C6A.jpg

那每個格子的移動代表什么呢, 如下是來自另一個參考文獻(xiàn)的敘述圖, 與上圖是倒過來的關(guān)系:

6CF5CEEB503BB48E722F56DDA53FEF0E.png

我們以其中紫色的那個格子值為4的來作為例子, 可以這樣理解, 該格子對應(yīng)著的X字符是N, Y字符串是E, 此處可以認(rèn)為由#INTEN轉(zhuǎn)化為#E, 需要進(jìn)行4次操作, 刪除I, N, T, N四個元素, 變?yōu)?E, 或者我們可以認(rèn)為從#E變到#INTEN需要最少進(jìn)行四步操作, 即增加INTN這4個元素,我們不要考慮#E增加了四個元素其后面序列就向后移動4位, 我們假設(shè)現(xiàn)在Y序列就只有#E, 沒有后面的元素, 我們再來看一下黃框中的元素, 其中3可以看做#E變?yōu)?IN需要三步, 刪除E, 加I, 加N, 那么此時4代表由#EX變?yōu)?IN在#E已經(jīng)變?yōu)?IN的基礎(chǔ)上還需要最少幾步, 那么就是4步, 多出的一步就是刪除#EX中的X, 因為#E已經(jīng)用3步變?yōu)?IN了, 即可以看做現(xiàn)在是#INX變?yōu)?IN需要多少步, 那當(dāng)然只需要多一步了, 當(dāng)然其實這么來說不準(zhǔn)確, 因為4不一定是由3+1得到的, 也可能是4的左下的2經(jīng)過2+2得到的, 也可能是4下面那個3通過+1得到的。

根據(jù)上圖, 可以認(rèn)為下圖矩陣中向右移動代表刪除, 因為從#E到#EX就是刪除了一位元素, 所以此時來考慮添加元素會導(dǎo)致整體后半序列向后移動的問題, 因為我們的目標(biāo)是得到右上角的值, 所以在這過程中我們可能先向上移動(增加), 再向右移動(刪除), 或者斜向右上角走一步(替換), 而我們的子狀態(tài)可以認(rèn)為是在上個字符串中所需步數(shù), 即假如Y字符串(底部的字符串)是#EX, 如果要變?yōu)?INTEN的話需要4步, 那么如果字符串是#EX呢, 則需要5步, 那如果是#EXE呢, 那么需要6步, 這么一步一步, 每一步可以利用上一步的結(jié)論, 直到最后#EXECUTION變?yōu)?INTEN需要多少步, 但是我們希望得到右上角的元素, 即#EXECUTION完全變成#INTENTION, 總共需要8步。 不要想得過于復(fù)雜要是Y字符串往里邊添加元素后邊序列又移怎么辦, 我們每次子狀態(tài)只是考慮當(dāng)前的序列, 而下次序列只是利用當(dāng)前序列得到的結(jié)論, 如果發(fā)現(xiàn)多了一位元素的話要刪除的話就刪除, 這樣就不會有多出來的序列了, 這么一來總有一條最佳路徑走到右上角的

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

AFAA5B9452E1C3FB85C1EB5715C69319.png

代碼實現(xiàn):

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')

同理, 這道題也能用之前的背包問題類似的簡化空間復(fù)雜度的方法, 用滾動數(shù)組, 即每次迭代下一行的時候只需要把之前的那一行保留下來就行, 因為只需要之前那一行的數(shù)據(jù):

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)(單調(diào)棧問題)

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

這道題可以用動態(tài)規(guī)劃或者分治算法, 如果用動態(tài)規(guī)劃的話如下圖

整個流程

代碼如下:

def largestRectangleArea(heights):
    stack,max_area=[-1],0
    for i in range(len(heights)):
        #若當(dāng)前位置中的比stack中最頂上的元素還要小, 那么就將該元素取出, 算當(dāng)前元素到取出元素所圍成的面積大小
        #將得到的結(jié)果與max_area比較, 然后再比較當(dāng)前stack最頂上元素是否大于當(dāng)前元素, 如果大于的話繼續(xù)取出來
        #其中stack中存的是下標(biāo), 而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行中第二列(下標(biāo)從0開始算)即 matrix[1][2] 此時的histogram的高度等于2, 即等于matrix[0][2]的 1 加上matrix[1][2]的1, 如果碰到像 matrix[1][1]中的0, 則將當(dāng)前的從上到下的累積高度清空

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算法不同的僅僅是此處計算了一下在當(dāng)前行每個列所對應(yīng)的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看成多個直方圖, 每一行及其上方的數(shù)據(jù)都構(gòu)成一個直方圖, 需要考察matrix.size()個直方圖
• 對于每個點(row, col), 我們最后都計算以這個點上方的連續(xù)的'1'往left, right方向延申可以得到的最大的矩形的面積
• 通過這種方法獲取的矩形一定會把最大的矩形包含在內(nèi)
• height[row][col]記錄的是(row, col)這個坐標(biāo)為底座的直方圖柱子的高度, 如果這個點是'0', 那么高度當(dāng)然是0了
• left[row][col]記錄的是(row, col)這個坐標(biāo)點對應(yīng)的height可以延申到的最左邊的位置
• right[row][col]記錄的是(row, col)這個坐標(biāo)點對應(yīng)的height可以延申到的最右邊的位置+1
• 以上面的matrix為例, 其中index從0開始
• 對于(row=2, col=1)這個點, left=0 (此處left和right指代的是下標(biāo), 而不是1的數(shù)量), 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卻已經(jīng)變化如此之大了, 這是因為left和right除了受左右兩邊的'1'影響, 還受到了其上方連續(xù)的'1'的制約
• 由于點(2,2)上有height=3個'1', 這幾個'1'的left的最大值作為當(dāng)前點的left, 這幾個'1'的right的最小值作為當(dāng)前點的right
• 因此, 實際上, 我們是要找以hight對應(yīng)的這條線段往左右兩邊移動(只能往全是'1'的地方移動), 可以掃過的最大面積
• 當(dāng)hight與目標(biāo)最大矩形區(qū)域的最短的height重合時, 最大矩形的面積就找到了, 如上面的例子, 就是點(2,3)或(2,4)對應(yīng)的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

**思路過程: **如果采用暴力破解的方式, 復(fù)雜度為 n*(n-1)*(n-2)*(n-3)…..復(fù)雜度為O(n!), 此時我們需要思考在暴力破解的方式中有哪部分是冗余的, 因此我們想到能不能將列表分成多個部分, 但是分為多個部分, 但是隨著氣球的爆炸不同部分間會合并到一起, 由于當(dāng)前情況下所能得到最大程度的coins不依賴于已經(jīng)爆炸的氣球, 所以我們考慮采用memorization方式, 由于每次爆炸所能得到的coin的式子是nums[i-1]*nums[i]*nums[i+1], 而我們此時當(dāng)只剩一個氣球的時候, 此時所能得到的coin是nums[0-1]*nums[i]*nums[n], 注意其中nums的下標(biāo)是從0到n-1, 所以此處nums[0-1]=nums[-1]和nums[n]取不到值 (此處不是python, -1取不到值), 由題目得又可寫成1*nums[i]*1. 那么我們對n個氣球中的每一個都計算一次當(dāng)其為最后一個爆炸的氣球的情況。

此時我們在假定 i 為最后一個爆炸的氣球后, 最開始的氣球隊列nums就可以分成兩部分, 一個是 i 左邊的部分, 一個是 i 右邊的部分, 因為 i 是最后一個爆炸的氣球, 所以左邊部分和右邊部分無論如何都合并不了(因為合并了就說明 i 已經(jīng)爆炸了, 但 i 是最后一個爆炸的) , 也就是說左邊和右邊部分此時可以獨立考慮, 所以此時問題轉(zhuǎn)變?yōu)? 左邊部分的哪種爆炸順序能最大化所得coins的值和右邊部分哪種爆炸順序能最大化所得的coins的值

既然能分為左右兩獨立部分, 此時應(yīng)該想到帶memorization的遞歸, 即假如現(xiàn)在認(rèn)為 i 為最后一個爆炸的, 將左部分遞歸, 此時左部分變?yōu)檎麄€輸入列表, 再對這個輸入列表做迭代, 認(rèn)為 j 是最后一個爆炸的, 再分為兩部分再遞歸, 以此循環(huán), 就有如下分治算法代碼, 注意, 第一次以 i 作為最后爆炸氣球時, 是計算 nums[-1]*nums[i]*nums[n] , 而分開后變?yōu)樽笥覂蓚€序列后, 假如設(shè)定 j 是左序列中最后一個爆的, 那么此時就是 nums[left-1]*nums[j]*nums[right+1], 但實際上 j 相當(dāng)于倒數(shù)第二個或者第三個爆的 (左右兩個分部不確定那個先)

def maxCoins(nums):
    #這一步確保了將nums中所有為0的值都去掉, 因為沒有意義
    #為了避免出現(xiàn)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]
            #當(dāng)輸入整個序列時, left=0, right=len(nums)-1, 所以會產(chǎn)生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]))

如果采用動態(tài)規(guī)劃的話, 過程如下, 其中 i 和 j 中間的間隔是當(dāng)選這個間隔內(nèi)的某一個氣球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 可以認(rèn)為是上式中的leftmost和rightmost, 因為較為清晰所以用leftmost和rightmost代替, 其中g(shù)rid[left][most]指代的在leftmost和rightmost區(qū)間內(nèi)所能得到最大的coin值, 很顯然, 最后要求的是 (i=0, j=length) 區(qū)域內(nèi)最大coins數(shù)量

流程-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):
        #截止到此處, 上面兩個循環(huán)是確保從左到右, 從底向上將dp矩陣每個值更新
            for k in range(i,j+1):
                #此處就是上面遞歸方法中的通項公式
                #其中g(shù)rid[i][j]等于在left~right區(qū)間中, 根據(jù)其中每一個值將列表分為兩半時, 得到的最大值
                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的相當(dāng)是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]

由此可見, 聯(lián)想遞歸過程, 假如第一輪選中了wordDict[3]=’aaaa’, 走到了s[4]這個位置, 然后在s[:4]=‘a(chǎn)aaa’的基礎(chǔ)上, 發(fā)現(xiàn)遍歷wordDict中所有元素, 都無法找到’b’, 那么就說明, s[4]這個位置是行不通的, 此時memo[4]=False, 所以如果通過wordDict[0]+wordDict[2]=‘a(chǎn)’+’aaa’到達(dá)了s[4]這個位置, 直接查閱memo[4]發(fā)現(xiàn)是False, 那么就沒有必要又在該位置重新迭代一遍word[Dict]了。

將遞歸拆成循環(huán), 就有了下邊的動態(tài)規(guī)劃解法:

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. 動態(tài)規(guī)劃與樹結(jié)合

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:

當(dāng)input為3時所有可能的樹

注意此處是二叉搜索樹, 中序遍歷會產(chǎn)生從小到大的序列。

/*
在這個問題中, 我們思考兩個問題:

1)我們要遍歷每一個可能的根節(jié)點, 假如輸入是5的話, 我們需要遍歷 1,2,3,4,5 分別將其作為根節(jié)點。 因為數(shù)列是有序的, 那么當(dāng)某個數(shù)被作為根節(jié)點時, 整個數(shù)列會被其分開為左右兩部分, 我們現(xiàn)在假設(shè)G(i)代表當(dāng)數(shù)列被以i為中心分為兩半時, 所能得到unique BST的數(shù)量。假設(shè) 1,2,3,4,5 被3從中間分開, 那么 左邊就是 1,2 右邊就是 4,5。很顯然, 左右兩邊是完全獨立的, 也就是說, G(3)的值為 左樹的所有排列組合*右樹的所有排列組合。也就是相當(dāng)于左樹和右樹的笛卡爾積。

2)我們接著來思考第二個問題, 此時左樹為1,2右樹為4,5 。那么此時左樹的所有可能的排列組合的數(shù)目是不是等于右樹的。那么也就是說, 排列組合的數(shù)目跟數(shù)字的具體內(nèi)容無關(guān), 而跟數(shù)字的數(shù)量有關(guān)。假如我們現(xiàn)在用兩個數(shù)組成一個二叉搜索樹, 那么無論這兩個點是(1,2)或是(4,5)還是(8,9)。  其可能的排列組合結(jié)果數(shù)量都是2。也就是說G(2)=2。

3) 那如果現(xiàn)在是三個點的一個數(shù)列呢, 譬如[1,2,3], 那G(3)等于多少? 
    我們首先將1作為根節(jié)點, 此時左樹為[], 右樹為[2,3]; 那么此時的值為 G(0)*G(2)
    接著我們將2作為根節(jié)點, 此時左樹為[1], 右樹為[3]; 那么此時的值為 G(1)*G(1)
    最后我們將3作為根節(jié)點, 此時左樹為[1,2], 右樹為[]; 那么此時的值為 G(2)*G(0)
    
    那么最后 G(3)=G(0)*G(2)+G(1)*G(1)+G(2)*G(0)

那么此時就很明了了, 我們只需要將狀態(tài)累積下來, 每一輪做累加即可。下面代碼中的grid就相當(dāng)于是G

*/
int numTrees(int n) {
        vector<int> grid(n+1);  //因為我們要取到n本身, 所以如果從下標(biāo)0開始的話需要一共取n+1個數(shù)
        grid[0]=grid[1]=1;
        for(int right_bound=2;right_bound<=n;right_bound++){  //grid[0]和grid[1]都已經(jīng)給出, 可以直接從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];
    }