動態(tài)規(guī)劃原理
動態(tài)規(guī)劃算法將待求解問題拆分成一系列相互交疊的子問題，通過遞推關系定義各子問題的求解策略，并隨時記錄子問題的解，最終獲得原始問題的解，避免了對交疊子問題的重復求解。
動態(tài)規(guī)劃要領
在動態(tài)規(guī)劃算法中有三要素，即最優(yōu)子結構、邊界和狀態(tài)轉移函數(shù)。
最優(yōu)子結構：每個階段的最優(yōu)狀態(tài)可以從之前某個階段的某個或某些狀態(tài)直接得到；
邊界：問題最小子集的解；
狀態(tài)轉移函數(shù)：從一個階段向另一個階段過渡的具體模式，描述的是兩個相鄰子問題之間的關系。
最長上升子序列問題
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
1.示例
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。
2.解題思路：
狀態(tài)定義：
創(chuàng)建與輸入列表nums相同長度的列表dp，dp[i]的值代表nums前i個數(shù)字的最長子序列長度。
3.最優(yōu)子結構：
當計算dp[i]時，我們需要遍歷[0,i)的列表區(qū)間做出判斷（j∈[0,i））：
（1）當nums[i]>nums[j]時，此時為上升子序列，所以此時dp[i]=dp[j]+1
（2）當nums[i]>nums[j]時，此時不是上升子序列跳過
4.轉移方程：dp[i]=max(dp[i],dp[j]+1)
5.初始狀態(tài)：每個元素至少可以單獨成為子序列，所有dp列表所有元素初始值為1
class Solution:
def lengthOfLIS(self, nums) :
len_nums=len(nums)
dp=[1 for i in range(len_nums)]
for i in range(1,len_nums):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
總結
以上就是本篇文章全部內容，才開始學習動態(tài)規(guī)劃的萌新沒看懂不要著急，動態(tài)規(guī)劃的代碼是有跡可循的，需要大家多多練習類似的題目。對于大家來說這道題還有另外的解法，希望各位讀者們多多交流，將你們的代碼發(fā)表在留言區(qū)供大家參考。
END主 編 | 王楠嵐
責 編 | KeeCTh
能力越強，責任越大。實事求是，嚴謹細致。
——where2go 團隊
微信號：算法與編程之美
