動(dòng)態(tài)規(guī)劃的核心就是將問題分解成子問題,然后推導(dǎo)出公式,根據(jù)公式利用以前計(jì)算的結(jié)果進(jìn)行計(jì)算.它需要枚舉出所有的可能,和貪心算法不一樣.
但是問題的難點(diǎn)在于,如何將問題分解并推導(dǎo)出公式呢.
比如可以枚舉當(dāng)前元素的狀態(tài),從而獲得所有的可能.
先從Leetcode中簡(jiǎn)單的題目開始練習(xí)吧.

Leetcode 53. Maximum Subarray

需要計(jì)算連續(xù)子序列最大的和.
Example:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

通常能想到的解法是這樣的:
如果前面累加的和已經(jīng)小于0,那么與當(dāng)前的值累加,只會(huì)比當(dāng)前值小,可以丟棄.起始點(diǎn)就從當(dāng)前值開始繼續(xù)累加;
如果前面累加的和大于0,那么就可以繼續(xù)累加當(dāng)前值:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        total = nums[0]
        res = total
        for i in range(1, len(nums)):
            if total <= 0:
                total = nums[i]
            else:
                total += nums[i]
            res = max(res, total)
        return res

乍一看,好像和動(dòng)態(tài)規(guī)劃有那么一點(diǎn)關(guān)系,但是卻不是那么明朗的關(guān)系.所以每次我隔很久做的時(shí)候,都會(huì)因?yàn)檫@個(gè)邏輯想上一會(huì).如果嘗試用動(dòng)態(tài)規(guī)劃的思路來描述并解決它呢?
假設(shè)對(duì)于nums中的每一個(gè)位置i的元素,可以有兩種情況:

1. 出現(xiàn)在了累加的子序列中,即這次累加包含了nums[i]
2. 沒有出現(xiàn),即這次我們還是采納以前的累加nums[k:m],其中m<i
   那么,據(jù)此我們可以有兩個(gè)數(shù)組記錄累加和:

# 包含了nums[i]的累加和
dp = [float('-inf')] * len(nums) # dp[0] = nums[0]
# 不包含nums[i]
fun = [float('-inf')] * len(nums)

于是dp的值可以有兩種取值:

1. 跟上i-1結(jié)尾的序列后
2. 自己為序列的開始

dp[i] = max(dp[i-1]+nums[i], nums[i])

而fun的取值呢,也有兩種:

1. 采用以i-1為結(jié)尾的累加和
2. 采用不以i-1為結(jié)尾的累加和

fun[i] = max(dp[i-1], fun[i-1])

所以可以寫出第一個(gè)版本的答案如下:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [float('-inf')] * len(nums)
        fun = [float('-inf')] * len(nums)
        dp[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i]+dp[i-1])
            fun[i] = max(dp[i-1], fun[i-1])
            res = max(res, dp[i], fun[i])
        return res

可以發(fā)現(xiàn),無(wú)論是dp還是fun,每次利用的都是前一個(gè)值,所以并不需要保存所有的中間值,因此將數(shù)組去掉,于是就有了第二個(gè)版本:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = nums[0]
        fun = float('-inf')
        res = nums[0]
        for i in range(1, len(nums)):
            prev_d, prev_f = dp, fun
            dp = max(nums[i], nums[i]+prev_d)
            fun = max(prev_d, prev_f)
            res = max(res, dp, fun)
        return res

在很多時(shí)候,這種方式已經(jīng)夠了,但是是否可以再精簡(jiǎn)一下呢?
注意到這句:

fun = max(prev_d, prev_f)

也就是說fun的值取決于dp的歷史值以及它自身的歷史值,但是fun的初始值是float(-'inf'),也就是實(shí)際上它是依賴于dp的值而變化的,那么對(duì)它的記錄與比較就是冗余的了,將它去掉,也就有了第三個(gè)版本:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            dp = max(nums[i], nums[i]+dp)
            res = max(res, dp)
        return res

其實(shí)最后就說明了一件事:要么就加上nums[i],要么,就從nums[i]開始.而最開始的解法,只是更詳細(xì)的描述了,在什么情況下,我們應(yīng)該加上它,而什么時(shí)候又應(yīng)該從它開始.

手里拿著錘子,看見什么都想釘一釘,再試試下面這題.

Leetcode 152. Maximum Product Subarray

計(jì)算連續(xù)子序列的最大積.
Example:

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

如果還繼續(xù)用上一題的思路最開始的解法,想著根據(jù)前序序列的正負(fù),來決定是否要乘上當(dāng)前值,情況就有點(diǎn)復(fù)雜了.因?yàn)樽畲笾涤锌赡軄碓从谝郧靶蛄械淖畲笾蹬c當(dāng)前值相乘,也有可能是最小值與當(dāng)前值相乘.
因此,將問題擴(kuò)展一下,不止記錄是否乘上了當(dāng)前值,還要記錄乘上的最大值和最小值:

c = [float('-inf')] * len(nums)  #contains i max
mc = [float('inf')] * len(nums)  #contains i min
n = [float('-inf')] * len(nums)  #not contains i max
mn = [float('inf')] * len(nums)  #not contains i min

那么,可以寫出第一個(gè)版本的答案:

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        c = [float('-inf')] * len(nums)  #contains i max
        mc = [float('inf')] * len(nums)  #contains i min
        n = [float('-inf')] * len(nums)  #not contains i max
        mn = [float('inf')] * len(nums)  #not contains i min


        c[0] = mc[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            c[i] = max(nums[i], c[i-1]*nums[i], mc[i-1]*nums[i])
            mc[i] = min(nums[i], mc[i-1]*nums[i], c[i-1]*nums[i])
            n[i] = max(c[i-1], n[i-1])
            mn[i] = min(mc[i-1], mn[i-1])
            res = max(res, n[i], c[i], mc[i], mn[i])
        return res

可以看出,只是在取最大值最小值的時(shí)候不放心,將以前的最大值和最小值都拿出來計(jì)算得出了結(jié)果.保證c[i]一定是乘上了nums[i]最大的值,因此n[i]一定是不包含nums[i]的最大的值.
既然是這樣,那么在確定res的時(shí)候,就不需要和mc[i]以及mn[i]進(jìn)行比較了.而mn的值也只有自己用上了,也可以去掉了:

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        c = [float('-inf')] * len(nums)  #contains i max
        mc = [float('inf')] * len(nums)  #contains i min
        n = [float('-inf')] * len(nums)  #not contains i max


        c[0] = mc[0] = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            c[i] = max(nums[i], c[i-1]*nums[i], mc[i-1]*nums[i])
            mc[i] = min(nums[i], mc[i-1]*nums[i], c[i-1]*nums[i])
            n[i] = max(c[i-1], n[i-1])
            res = max(res, n[i], c[i])
        return res

再次發(fā)現(xiàn),可以不用數(shù)組存儲(chǔ)中間的狀態(tài),于是再精簡(jiǎn)一次:

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = float('-inf')
        c = mc = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            prev_c, prev_mc, prev_n = c, mc, n
            c = max(nums[i], prev_c*nums[i], prev_mc*nums[i])
            mc = min(nums[i], prev_mc*nums[i], prev_c*nums[i])
            n = max(prev_c, prev_n)
            res = max(res, n, c)
        return res

然后又能發(fā)現(xiàn)和上題一樣的問題,n的值取決于c的值,所以最終的版本也不再需要n了:

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        c = mc = nums[0]
        res = nums[0]
        for i in range(1, len(nums)):
            prev_c, prev_mc = c, mc
            c = max(nums[i], prev_c*nums[i], prev_mc*nums[i])
            mc = min(nums[i], prev_mc*nums[i], prev_c*nums[i])
            res = max(res, c)
        return res

雖然比起大神的解答還有差距,但是至少不會(huì)再忘記了~
其實(shí)總結(jié)起來也就是枚舉了所有的可能,只不過采用了max,過濾掉了一些不符合的情況,也就是進(jìn)行了剪枝.
類似的問題還有(待更新):
經(jīng)典的爬樓梯:Leetcode 70. Climbing Stairs