動態規劃的狀態轉移方程一般不容易找出來，并且兩個變數的動態規劃也不容易直接寫出，我以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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412981.html
標籤：其他
下一篇：7-1 列印沙漏