看這個就夠了

動態規劃的狀態轉移方程一般不容易找出來，并且兩個變量的動態規劃也不容易直接寫出，我以leetcode No.300 最長遞增子序列為例，總結一下是如何一步步從最開始的遞歸做法到記憶化搜索再到動態規劃的。
首先題目如下：
給你一個整數數組 nums ，找到其中最長嚴格遞增子序列的長度。
子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。

示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：
輸入：nums = [7,7,7,7,7,7,7]
輸出：1

遞歸

如果一眼動態規劃的題目沒有思路，不妨先從遞歸開始一步步變成動態規劃

以[1,3,2,5,7,4]為例

暴力解法（遞歸）：

• 從1開始的話，要選比它大的數字，那么遍歷后續數組下一個數字可以選3或者5或者7或者4

• 選[1,3]后，繼續遍歷后續數組，直到最后一位。

• 要注意的是每次選擇數字后，遞增序列長度就+1，然后要比較是否是最長序列。

• 每一次遍歷的過程就是一次遞歸。

• 由于序列不一定從1開始，從頭對每個數組都做一次遞歸。

代碼

class Solution:

  def findLengthOfLCIS(self, nums) -> int:

     maxnum = 0

     for i in range(len(nums)):

       maxnum = max(maxnum,self.digui(nums,i))

     return maxnum

  

  def digui(self,nums,i):

     maxnum = 1



     if i == len(nums)-1:

       return 1

     for j in range(i+1,len(nums)):

       if nums[j] > nums[i]:

         maxnum = max(maxnum,self.digui(nums,j)+1)

     return maxnum

記憶化搜索

然后會發現，我進行了很多重復的計算，比如在最開始選1的時候,我計算了2的遞增序列長度，在選[1,3]后我又要計算了2的遞增長度

于是，我們可以創建一個memo數組，在第一次計算完2的遞增序列長度后，將其保存下來，下次直接查找就可以使用。

這就是記憶化搜索。

代碼

class Solution:

  memo = []

  def findLengthOfLCIS(self, nums) -> int:

     self.memo = [0]*len(nums)

     maxnum = 0

     for i in range(len(nums)):

       maxnum = max(maxnum,self.digui(nums,i))

     return maxnum

  

  def digui(self,nums,i):

     maxnum = 1

     if i in self.memo:

       return self.memo[i]

     if i == len(nums)-1:

       return 1

     for j in range(i+1,len(nums)):

       if nums[j] > nums[i]:

         maxnum = max(maxnum,self.digui(nums,j)+1)

     self.memo[i] = maxnum

     return maxnum

動態規劃

我們注意到這個時候，已經幾乎寫出來了狀態轉移方程

if nums[j] > nums[i]:

maxnum = max(maxnum,self.digui(nums,j)+1)

memo數組就相當于dp數組，其中存放的是每個數的最大遞增序列長度

我們從后往前遍歷一遍nums就可以了

代碼

最終動態規劃代碼：

class Solution:

  def lengthOfLIS(self, nums) -> int:

     if nums == []:

       return 0

     dp = [1]*len(nums)

     

     for i in range(len(nums)-1,-1,-1):

       #print(i)

       for j in range(i+1,len(nums)):

         if nums[i] < nums[j]:

           dp[i] = max(dp[i],dp[j] + 1)

     #print(dp)

     return max(dp)