看一遍就理解：動(dòng)態(tài)規(guī)劃詳解
今日推薦
為什么不建議你用a.equals(b)判斷對(duì)象相等
SpringBoot中的線程池，你真的會(huì)用么？ 代碼對(duì)比工具，就用這7個(gè)！ 在 IDEA 中的各種調(diào)試技巧，輕松定位 Bug（超級(jí)全面）
前言
我們刷leetcode的時(shí)候，經(jīng)常會(huì)遇到動(dòng)態(tài)規(guī)劃類型題目。動(dòng)態(tài)規(guī)劃問題非常非常經(jīng)典，也很有技巧性，一般大廠都非常喜歡問。今天跟大家一起來學(xué)習(xí)動(dòng)態(tài)規(guī)劃的套路，文章如果有不正確的地方，歡迎大家指出哈，感謝感謝~
什么是動(dòng)態(tài)規(guī)劃？ 動(dòng)態(tài)規(guī)劃的核心思想 一個(gè)例子走進(jìn)動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)規(guī)劃的解題套路 leetcode案例分析
公眾號(hào)：撿田螺的小男孩
什么是動(dòng)態(tài)規(guī)劃？
動(dòng)態(tài)規(guī)劃（英語：Dynamic programming，簡(jiǎn)稱 DP），是一種在數(shù)學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)、經(jīng)濟(jì)學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。
★dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
”
以上定義來自維基百科，看定義感覺還是有點(diǎn)抽象。簡(jiǎn)單來說，動(dòng)態(tài)規(guī)劃其實(shí)就是，給定一個(gè)問題，我們把它拆成一個(gè)個(gè)子問題，直到子問題可以直接解決。然后呢，把子問題答案保存起來，以減少重復(fù)計(jì)算。再根據(jù)子問題答案反推，得出原問題解的一種方法。
★一般這些子問題很相似，可以通過函數(shù)關(guān)系式遞推出來。然后呢，動(dòng)態(tài)規(guī)劃就致力于解決每個(gè)子問題一次，減少重復(fù)計(jì)算,比如斐波那契數(shù)列就可以看做入門級(jí)的經(jīng)典動(dòng)態(tài)規(guī)劃問題。
”
動(dòng)態(tài)規(guī)劃核心思想
動(dòng)態(tài)規(guī)劃最核心的思想，就在于拆分子問題，記住過往，減少重復(fù)計(jì)算。
我們來看下，網(wǎng)上比較流行的一個(gè)例子：
★”
A ："1+1+1+1+1+1+1+1 =？" A ："上面等式的值是多少" B ：計(jì)算 "8" A : 在上面等式的左邊寫上 "1+" 呢？ A : "此時(shí)等式的值為多少" B : 很快得出答案 "9" A : "你怎么這么快就知道答案了" A : "只要在8的基礎(chǔ)上加1就行了" A : "所以你不用重新計(jì)算，因?yàn)槟阌涀×说谝粋€(gè)等式的值為8!動(dòng)態(tài)規(guī)劃算法也可以說是 '記住求過的解來節(jié)省時(shí)間'"
一個(gè)例子帶你走進(jìn)動(dòng)態(tài)規(guī)劃 -- 青蛙跳階問題
暴力遞歸
★leetcode原題：一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)臺(tái)階。求該青蛙跳上一個(gè) 10 級(jí)的臺(tái)階總共有多少種跳法。
”
有些小伙伴第一次見這個(gè)題的時(shí)候，可能會(huì)有點(diǎn)蒙圈，不知道怎么解決。其實(shí)可以試想：
★”
要想跳到第10級(jí)臺(tái)階，要么是先跳到第9級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第8級(jí)，然后一次邁2級(jí)臺(tái)階上去。 同理，要想跳到第9級(jí)臺(tái)階，要么是先跳到第8級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第7級(jí)，然后一次邁2級(jí)臺(tái)階上去。 要想跳到第8級(jí)臺(tái)階，要么是先跳到第7級(jí)，然后再跳1級(jí)臺(tái)階上去;要么是先跳到第6級(jí)，然后一次邁2級(jí)臺(tái)階上去。
假設(shè)跳到第n級(jí)臺(tái)階的跳數(shù)我們定義為f(n)，很顯然就可以得出以下公式：
f（10） = f（9）+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)
...
f(3) = f(2) + f(1)
即通用公式為: f(n) = f(n-1) + f(n-2)
那f(2) 或者 f(1) 等于多少呢？
當(dāng)只有2級(jí)臺(tái)階時(shí)，有兩種跳法，第一種是直接跳兩級(jí)，第二種是先跳一級(jí)，然后再跳一級(jí)。即f(2) = 2; 當(dāng)只有1級(jí)臺(tái)階時(shí)，只有一種跳法，即f（1）= 1；
因此可以用遞歸去解決這個(gè)問題：
class Solution {
public int numWays(int n) {
if(n == 1){
return 1;
}
if(n == 2){
return 2;
}
return numWays(n-1) + numWays(n-2);
}
}
去leetcode提交一下，發(fā)現(xiàn)有問題，超出時(shí)間限制了
為什么超時(shí)了呢？遞歸耗時(shí)在哪里呢？先畫出遞歸樹看看：
要計(jì)算原問題 f(10)，就需要先計(jì)算出子問題 f(9) 和 f(8) 然后要計(jì)算 f(9)，又要先算出子問題 f(8) 和 f(7)，以此類推。 一直到 f(2) 和 f(1），遞歸樹才終止。
我們先來看看這個(gè)遞歸的時(shí)間復(fù)雜度吧：
遞歸時(shí)間復(fù)雜度 = 解決一個(gè)子問題時(shí)間*子問題個(gè)數(shù)
一個(gè)子問題時(shí)間 = f（n-1）+f（n-2），也就是一個(gè)加法的操作，所以復(fù)雜度是 O(1)； 問題個(gè)數(shù) = 遞歸樹節(jié)點(diǎn)的總數(shù)，遞歸樹的總節(jié)點(diǎn) = 2^n-1，所以是復(fù)雜度O(2^n)。
因此，青蛙跳階，遞歸解法的時(shí)間復(fù)雜度 = O(1) * O(2^n) = O(2^n)，就是指數(shù)級(jí)別的，爆炸增長(zhǎng)的，如果n比較大的話，超時(shí)很正常的了。
回過頭來，你仔細(xì)觀察這顆遞歸樹，你會(huì)發(fā)現(xiàn)存在大量重復(fù)計(jì)算，比如f（8）被計(jì)算了兩次，f（7）被重復(fù)計(jì)算了3次...所以這個(gè)遞歸算法低效的原因，就是存在大量的重復(fù)計(jì)算！
既然存在大量重復(fù)計(jì)算，那么我們可以先把計(jì)算好的答案存下來，即造一個(gè)備忘錄，等到下次需要的話，先去備忘錄查一下，如果有，就直接取就好了，備忘錄沒有才開始計(jì)算，那就可以省去重新重復(fù)計(jì)算的耗時(shí)啦！這就是帶備忘錄的解法。
帶備忘錄的遞歸解法（自頂向下）
一般使用一個(gè)數(shù)組或者一個(gè)哈希map充當(dāng)這個(gè)備忘錄。
第一步，f（10）= f(9) + f(8)，f(9) 和f（8）都需要計(jì)算出來，然后再加到備忘錄中，如下：
第二步， f(9) = f（8）+ f（7），f（8）= f（7）+ f(6), 因?yàn)?f(8) 已經(jīng)在備忘錄中啦，所以可以省掉，f(7),f（6）都需要計(jì)算出來，加到備忘錄中~
第三步， f(8) = f（7）+ f(6),發(fā)現(xiàn)f(8)，f(7),f（6）全部都在備忘錄上了，所以都可以剪掉。
所以呢，用了備忘錄遞歸算法，遞歸樹變成光禿禿的樹干咯，如下：
帶備忘錄的遞歸算法，子問題個(gè)數(shù)=樹節(jié)點(diǎn)數(shù)=n，解決一個(gè)子問題還是O(1),所以帶備忘錄的遞歸算法的時(shí)間復(fù)雜度是O(n)。接下來呢，我們用帶備忘錄的遞歸算法去擼代碼，解決這個(gè)青蛙跳階問題的超時(shí)問題咯~，代碼如下：
public class Solution {
//使用哈希map，充當(dāng)備忘錄的作用
Map<Integer, Integer> tempMap = new HashMap();
public int numWays(int n) {
// n = 0 也算1種
if (n == 0) {
return 1;
}
if (n <= 2) {
return n;
}
//先判斷有沒計(jì)算過，即看看備忘錄有沒有
if (tempMap.containsKey(n)) {
//備忘錄有，即計(jì)算過，直接返回
return tempMap.get(n);
} else {
// 備忘錄沒有，即沒有計(jì)算過，執(zhí)行遞歸計(jì)算,并且把結(jié)果保存到備忘錄map中，對(duì)1000000007取余（這個(gè)是leetcode題目規(guī)定的）
tempMap.put(n, (numWays(n - 1) + numWays(n - 2)) % 1000000007);
return tempMap.get(n);
}
}
}
去leetcode提交一下，如圖，穩(wěn)了：
其實(shí)，還可以用動(dòng)態(tài)規(guī)劃解決這道題。
自底向上的動(dòng)態(tài)規(guī)劃
動(dòng)態(tài)規(guī)劃跟帶備忘錄的遞歸解法基本思想是一致的，都是減少重復(fù)計(jì)算，時(shí)間復(fù)雜度也都是差不多。但是呢：
帶備忘錄的遞歸，是從f(10)往f(1）方向延伸求解的，所以也稱為自頂向下的解法。 動(dòng)態(tài)規(guī)劃從較小問題的解，由交疊性質(zhì)，逐步?jīng)Q策出較大問題的解，它是從f(1)往f(10）方向，往上推求解，所以稱為自底向上的解法。
動(dòng)態(tài)規(guī)劃有幾個(gè)典型特征，最優(yōu)子結(jié)構(gòu)、狀態(tài)轉(zhuǎn)移方程、邊界、重疊子問題。在青蛙跳階問題中：
f(n-1)和f(n-2) 稱為 f(n) 的最優(yōu)子結(jié)構(gòu) f(n)= f（n-1）+f（n-2）就稱為狀態(tài)轉(zhuǎn)移方程 f(1) = 1, f(2) = 2 就是邊界啦 比如f(10)= f(9)+f(8),f(9) = f(8) + f(7) ,f(8)就是重疊子問題。
我們來看下自底向上的解法，從f(1)往f(10）方向，想想是不是直接一個(gè)for循環(huán)就可以解決啦，如下：
帶備忘錄的遞歸解法，空間復(fù)雜度是O(n)，但是呢，仔細(xì)觀察上圖，可以發(fā)現(xiàn)，f（n）只依賴前面兩個(gè)數(shù)，所以只需要兩個(gè)變量a和b來存儲(chǔ)，就可以滿足需求了，因此空間復(fù)雜度是O(1)就可以啦
動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)代碼如下：
public class Solution {
public int numWays(int n) {
if (n<= 1) {
return 1;
}
if (n == 2) {
return 2;
}
int a = 1;
int b = 2;
int temp = 0;
for (int i = 3; i <= n; i++) {
temp = (a + b)% 1000000007;
a = b;
b = temp;
}
return temp;
}
}
動(dòng)態(tài)規(guī)劃的解題套路
什么樣的問題可以考慮使用動(dòng)態(tài)規(guī)劃解決呢？
★如果一個(gè)問題，可以把所有可能的答案窮舉出來，并且窮舉出來后，發(fā)現(xiàn)存在重疊子問題，就可以考慮使用動(dòng)態(tài)規(guī)劃。
”
比如一些求最值的場(chǎng)景，如最長(zhǎng)遞增子序列、最小編輯距離、背包問題、湊零錢問題等等，都是動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用場(chǎng)景。
動(dòng)態(tài)規(guī)劃的解題思路
動(dòng)態(tài)規(guī)劃的核心思想就是拆分子問題，記住過往，減少重復(fù)計(jì)算。 并且動(dòng)態(tài)規(guī)劃一般都是自底向上的，因此到這里，基于青蛙跳階問題，我總結(jié)了一下我做動(dòng)態(tài)規(guī)劃的思路：
窮舉分析 確定邊界 找出規(guī)律，確定最優(yōu)子結(jié)構(gòu) 寫出狀態(tài)轉(zhuǎn)移方程
1. 窮舉分析
當(dāng)臺(tái)階數(shù)是1的時(shí)候，有一種跳法，f（1） =1 當(dāng)只有2級(jí)臺(tái)階時(shí)，有兩種跳法，第一種是直接跳兩級(jí)，第二種是先跳一級(jí)，然后再跳一級(jí)。即f(2) = 2; 當(dāng)臺(tái)階是3級(jí)時(shí)，想跳到第3級(jí)臺(tái)階，要么是先跳到第2級(jí)，然后再跳1級(jí)臺(tái)階上去，要么是先跳到第 1級(jí)，然后一次邁 2 級(jí)臺(tái)階上去。所以f(3) = f(2) + f(1) =3 當(dāng)臺(tái)階是4級(jí)時(shí)，想跳到第3級(jí)臺(tái)階，要么是先跳到第3級(jí)，然后再跳1級(jí)臺(tái)階上去，要么是先跳到第 2級(jí)，然后一次邁 2 級(jí)臺(tái)階上去。所以f(4) = f(3) + f(2) =5 當(dāng)臺(tái)階是5級(jí)時(shí)......
2. 確定邊界
通過窮舉分析，我們發(fā)現(xiàn)，當(dāng)臺(tái)階數(shù)是1的時(shí)候或者2的時(shí)候，可以明確知道青蛙跳法。f（1） =1，f(2) = 2，當(dāng)臺(tái)階n>=3時(shí)，已經(jīng)呈現(xiàn)出規(guī)律f(3) = f(2) + f(1) =3，因此f（1） =1，f(2) = 2就是青蛙跳階的邊界。
3. 找規(guī)律，確定最優(yōu)子結(jié)構(gòu)
n>=3時(shí)，已經(jīng)呈現(xiàn)出規(guī)律 f(n) = f(n-1) + f(n-2) ，因此，f(n-1)和f(n-2) 稱為 f(n) 的最優(yōu)子結(jié)構(gòu)。什么是最優(yōu)子結(jié)構(gòu)？有這么一個(gè)解釋：
★一道動(dòng)態(tài)規(guī)劃問題，其實(shí)就是一個(gè)遞推問題。假設(shè)當(dāng)前決策結(jié)果是f(n),則最優(yōu)子結(jié)構(gòu)就是要讓 f(n-k) 最優(yōu),最優(yōu)子結(jié)構(gòu)性質(zhì)就是能讓轉(zhuǎn)移到n的狀態(tài)是最優(yōu)的,并且與后面的決策沒有關(guān)系,即讓后面的決策安心地使用前面的局部最優(yōu)解的一種性質(zhì)
”
4， 寫出狀態(tài)轉(zhuǎn)移方程
通過前面3步，窮舉分析，確定邊界，最優(yōu)子結(jié)構(gòu)，我們就可以得出狀態(tài)轉(zhuǎn)移方程啦：
5. 代碼實(shí)現(xiàn)
我們實(shí)現(xiàn)代碼的時(shí)候，一般注意從底往上遍歷哈，然后關(guān)注下邊界情況，空間復(fù)雜度，也就差不多啦。動(dòng)態(tài)規(guī)劃有個(gè)框架的，大家實(shí)現(xiàn)的時(shí)候，可以考慮適當(dāng)參考一下：
dp[0][0][...] = 邊界值
for(狀態(tài)1 ：所有狀態(tài)1的值){
for(狀態(tài)2 ：所有狀態(tài)2的值){
for(...){
//狀態(tài)轉(zhuǎn)移方程
dp[狀態(tài)1][狀態(tài)2][...] = 求最值
}
}
}
leetcode案例分析
我們一起來分析一道經(jīng)典leetcode題目吧
★給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。
”
示例 1：
輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長(zhǎng)遞增子序列是 [2,3,7,101]，因此長(zhǎng)度為 4 。
示例 2：
輸入：nums = [0,1,0,3,2,3]
輸出：4
我們按照以上動(dòng)態(tài)規(guī)劃的解題思路，
窮舉分析 確定邊界 找規(guī)律，確定最優(yōu)子結(jié)構(gòu) 狀態(tài)轉(zhuǎn)移方程
1.窮舉分析
因?yàn)閯?dòng)態(tài)規(guī)劃，核心思想包括拆分子問題，記住過往，減少重復(fù)計(jì)算。 所以我們?cè)谒伎荚瓎栴}：數(shù)組num[i]的最長(zhǎng)遞增子序列長(zhǎng)度時(shí)，可以思考下相關(guān)子問題，比如原問題是否跟子問題num[i-1]的最長(zhǎng)遞增子序列長(zhǎng)度有關(guān)呢？
自底向上的窮舉
這里觀察規(guī)律，顯然是有關(guān)系的，我們還是遵循動(dòng)態(tài)規(guī)劃自底向上的原則，基于示例1的數(shù)據(jù)，從數(shù)組只有一個(gè)元素開始分析。
當(dāng)nums只有一個(gè)元素10時(shí)，最長(zhǎng)遞增子序列是[10],長(zhǎng)度是1. 當(dāng)nums需要加入一個(gè)元素9時(shí)，最長(zhǎng)遞增子序列是[10]或者[9],長(zhǎng)度是1。 當(dāng)nums再加入一個(gè)元素2時(shí)，最長(zhǎng)遞增子序列是[10]或者[9]或者[2],長(zhǎng)度是1。 當(dāng)nums再加入一個(gè)元素5時(shí)，最長(zhǎng)遞增子序列是[2,5],長(zhǎng)度是2。 當(dāng)nums再加入一個(gè)元素3時(shí)，最長(zhǎng)遞增子序列是[2,5]或者[2,3],長(zhǎng)度是2。 當(dāng)nums再加入一個(gè)元素7時(shí)，,最長(zhǎng)遞增子序列是[2,5,7]或者[2,3,7],長(zhǎng)度是3。 當(dāng)nums再加入一個(gè)元素101時(shí)，最長(zhǎng)遞增子序列是[2,5,7,101]或者[2,3,7,101],長(zhǎng)度是4。 當(dāng)nums再加入一個(gè)元素18時(shí)，最長(zhǎng)遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長(zhǎng)度是4。 當(dāng)nums再加入一個(gè)元素7時(shí),最長(zhǎng)遞增子序列是[2,5,7,101]或者[2,3,7,101]或者[2,5,7,18]或者[2,3,7,18],長(zhǎng)度是4.
分析找規(guī)律，拆分子問題
通過上面分析，我們可以發(fā)現(xiàn)一個(gè)規(guī)律：
如果新加入一個(gè)元素nums[i], 最長(zhǎng)遞增子序列要么是以nums[i]結(jié)尾的遞增子序列，要么就是nums[i-1]的最長(zhǎng)遞增子序列?？吹竭@個(gè)，是不是很開心，nums[i]的最長(zhǎng)遞增子序列已經(jīng)跟子問題 nums[i-1]的最長(zhǎng)遞增子序列有關(guān)聯(lián)了。
原問題數(shù)組nums[i]的最長(zhǎng)遞增子序列 = 子問題數(shù)組nums[i-1]的最長(zhǎng)遞增子序列/nums[i]結(jié)尾的最長(zhǎng)遞增子序列
是不是感覺成功了一半呢？但是如何把nums[i]結(jié)尾的遞增子序列也轉(zhuǎn)化為對(duì)應(yīng)的子問題呢？要是nums[i]結(jié)尾的遞增子序列也跟nums[i-1]的最長(zhǎng)遞增子序列有關(guān)就好了。又或者nums[i]結(jié)尾的最長(zhǎng)遞增子序列，跟前面子問題num[j]（0=<j<i）結(jié)尾的最長(zhǎng)遞增子序列有關(guān)就好了，帶著這個(gè)想法，我們又回頭看看窮舉的過程：
nums[i]的最長(zhǎng)遞增子序列，不就是從以數(shù)組num[i]每個(gè)元素結(jié)尾的最長(zhǎng)子序列集合，取元素最多（也就是長(zhǎng)度最長(zhǎng)）那個(gè)嘛，所以原問題，我們轉(zhuǎn)化成求出以數(shù)組nums每個(gè)元素結(jié)尾的最長(zhǎng)子序列集合，再取最大值嘛。哈哈，想到這，我們就可以用dp[i]表示以num[i]這個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度啦，然后再來看看其中的規(guī)律：
其實(shí)，nums[i]結(jié)尾的自增子序列，只要找到比nums[i]小的子序列，加上nums[i] 就可以啦。顯然，可能形成多種新的子序列，我們選最長(zhǎng)那個(gè)，就是dp[i]的值啦
★”
nums[3]=5,以 5結(jié)尾的最長(zhǎng)子序列就是[2,5],因?yàn)閺臄?shù)組下標(biāo)0到3遍歷，只找到了子序列[2]比5小，所以就是[2]+[5]啦，即dp[4]=2nums[4]=3,以 3結(jié)尾的最長(zhǎng)子序列就是[2,3],因?yàn)閺臄?shù)組下標(biāo)0到4遍歷，只找到了子序列[2]比3小，所以就是[2]+[3]啦，即dp[4]=2nums[5]=7，以 7結(jié)尾的最長(zhǎng)子序列就是[2,5,7]和[2,3,7],因?yàn)閺臄?shù)組下標(biāo)0到5遍歷，找到2,5和3都比7小，所以就有[2,7],[5,7],[3,7],[2,5,7]和[2,3,7]這些子序列，最長(zhǎng)子序列就是[2,5,7]和[2,3,7]，它倆不就是以5結(jié)尾和3結(jié)尾的最長(zhǎng)遞增子序列+[7]來的嘛！所以，dp[5]=3 =dp[3]+1=dp[4]+1。
很顯然有這個(gè)規(guī)律：一個(gè)以nums[i]結(jié)尾的數(shù)組nums
如果存在j屬于區(qū)間[0，i-1],并且num[i]>num[j]的話，則有: dp(i) =max(dp(j))+1，
最簡(jiǎn)單的邊界情況
當(dāng)nums數(shù)組只有一個(gè)元素時(shí)，最長(zhǎng)遞增子序列的長(zhǎng)度dp(1)=1,當(dāng)nums數(shù)組有兩個(gè)元素時(shí)，dp(2) =2或者1， 因此邊界就是dp(1)=1。
確定最優(yōu)子結(jié)構(gòu)
從窮舉分析，我們可以得出，以下的最優(yōu)結(jié)構(gòu)：
dp(i) =max(dp(j))+1，存在j屬于區(qū)間[0，i-1],并且num[i]>num[j]。
max(dp(j)) 就是最優(yōu)子結(jié)構(gòu)。
狀態(tài)轉(zhuǎn)移方程
通過前面分析，我們就可以得出狀態(tài)轉(zhuǎn)移方程啦：
所以數(shù)組nums[i]的最長(zhǎng)遞增子序列就是：
最長(zhǎng)遞增子序列 =max(dp[i])
代碼實(shí)現(xiàn)
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
//初始化就是邊界情況
dp[0] = 1;
int maxans = 1;
//自底向上遍歷
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
//從下標(biāo)0到i遍歷
for (int j = 0; j < i; j++) {
//找到前面比nums[i]小的數(shù)nums[j],即有dp[i]= dp[j]+1
if (nums[j] < nums[i]) {
//因?yàn)闀?huì)有多個(gè)小于nums[i]的數(shù)，也就是會(huì)存在多種組合了嘛，我們就取最大放到dp[i]
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
//求出dp[i]后，dp最大那個(gè)就是nums的最長(zhǎng)遞增子序列啦
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}
推薦文章
更多項(xiàng)目源碼