動態(tài)規(guī)劃在約束優(yōu)化問題中的應用方案一、引言

動態(tài)規(guī)劃（DynamicProgramming,DP）是一種解決復雜優(yōu)化問題的算法思想，通過將問題分解為子問題并存儲子問題的解（記憶化或自底向上）來避免重復計算，從而提高效率。約束優(yōu)化問題是指在優(yōu)化目標的同時，需要滿足一系列約束條件的數(shù)學問題。動態(tài)規(guī)劃在處理具有遞歸結構和重疊子問題時具有顯著優(yōu)勢，特別適用于資源分配、路徑規(guī)劃、生產(chǎn)調(diào)度等場景。

二、動態(tài)規(guī)劃的基本原理

動態(tài)規(guī)劃的核心思想是將原問題分解為多個子問題，并通過以下兩個關鍵特性實現(xiàn)優(yōu)化：

（一）最優(yōu)子結構

若問題的最優(yōu)解包含子問題的最優(yōu)解，則該問題具有最優(yōu)子結構。例如，最短路徑問題中，從起點到終點的最短路徑包含從中間節(jié)點到終點的最短路徑。

（二）重疊子問題

在遞歸求解過程中，多個子問題可能被重復計算。動態(tài)規(guī)劃通過存儲子問題的解（如使用數(shù)組或哈希表）來避免重復計算，降低時間復雜度。

三、動態(tài)規(guī)劃在約束優(yōu)化問題中的應用

動態(tài)規(guī)劃適用于具有以下特征的約束優(yōu)化問題：

（一）離散決策問題

在每一步選擇有限個決策，且決策序列決定最終結果。例如，背包問題中，每次只能選擇放入或不放入一個物品。

（二）可分解為子問題

原問題可表示為多個子問題的組合，且子問題之間相互獨立。例如，斐波那契數(shù)列的計算可分解為多個小的斐波那契數(shù)列計算。

（三）狀態(tài)轉(zhuǎn)移方程

\[

\text{狀態(tài)方程：}\quadS(i)=\min/max\{\text{決策}\times\text{收益}+S(i-1)\}

\]

其中，\(S(i)\)表示第\(i\)步的最優(yōu)狀態(tài)，決策影響當前收益和后續(xù)狀態(tài)。

四、應用步驟

（一）定義狀態(tài)

明確問題的狀態(tài)表示，通常用數(shù)組或哈希表存儲子問題的解。例如，在背包問題中，狀態(tài)表示為當前容量下的最大價值。

（二）確定狀態(tài)轉(zhuǎn)移方程

根據(jù)問題特性建立狀態(tài)轉(zhuǎn)移方程，確保子問題解的遞推關系正確。例如：

-背包問題：

\[

\text{dp}[i][j]=\max\{\text{dp}[i-1][j],\text{dp}[i-1][j-w[i]]+v[i]\}

\]

其中，\(w[i]\)為物品重量，\(v[i]\)為物品價值。

（三）初始化邊界條件

設定初始狀態(tài)，通常為第0步或第0容量時的解。例如：

\[

\text{dp}[0][j]=0,\quad\text{dp}[i][0]=0

\]

（四）計算最優(yōu)解

1.自底向上：從第1步到最終步逐層計算；

2.自頂向下：使用遞歸并存儲已計算結果。

五、示例：0/1背包問題

以0/1背包問題為例，說明動態(tài)規(guī)劃的應用：

（一）問題描述

給定物品重量和價值，以及背包容量，選擇物品放入背包使總價值最大，且總重量不超過背包容量。

（二）狀態(tài)定義

-狀態(tài)：\(dp[i][j]\)表示前\(i\)件物品在容量為\(j\)時的最大價值。

（三）狀態(tài)轉(zhuǎn)移方程

\[

dp[i][j]=\max\{dp[i-1][j],\quaddp[i-1][j-w[i]]+v[i]\}

\]

其中，若\(j<w[i]\)，則\(dp[i][j]=dp[i-1][j]\)。

（四）計算過程

1.初始化：

-\(dp[0][j]=0\)（未選擇物品時價值為0）；

-\(dp[i][0]=0\)（容量為0時價值為0）。

2.逐行計算：

-對于每個物品，更新當前容量下的最大價值。

（五）結果提取

最終解為\(dp[n][C]\)，其中\(zhòng)(n\)為物品數(shù)量，\(C\)為背包容量。

六、總結

動態(tài)規(guī)劃通過分解子問題、存儲解和建立狀態(tài)轉(zhuǎn)移方程，高效解決約束優(yōu)化問題。其應用的關鍵在于識別問題的最優(yōu)子結構和重疊子問題，并設計合理的狀態(tài)表示和轉(zhuǎn)移方程。通過以上步驟，可推廣至其他約束優(yōu)化問題，如資源分配、路徑規(guī)劃等。

五、示例：0/1背包問題（續(xù)）

（一）問題描述詳細闡述

0/1背包問題是最經(jīng)典的動態(tài)規(guī)劃應用之一，其約束條件清晰，適合通過動態(tài)規(guī)劃進行建模和求解。問題描述如下：

-輸入：

-一系列物品，每個物品有確定的重量（\(w[i]\)）和價值（\(v[i]\)）；

-背包的最大承載容量（\(C\)）。

-輸出：

-將哪些物品放入背包，使背包內(nèi)物品總價值最大，且總重量不超過背包容量。

-注意：每個物品只能選擇放入或不放入，不能分割。

示例：

假設有3件物品，重量分別為\[2,3,4\]，價值分別為\[3,4,5\]，背包容量為\(C=5\)。目標是選擇物品組合使總價值最大。

（二）狀態(tài)定義進一步說明

在動態(tài)規(guī)劃中，狀態(tài)表示為決策過程中的某個階段的最優(yōu)解。對于0/1背包問題，狀態(tài)定義如下：

-狀態(tài)表示：

-\(dp[i][j]\)表示從前\(i\)件物品中選取，且背包剩余容量為\(j\)時的最大價值。

-狀態(tài)維度：

-第一維\(i\)表示物品編號，范圍從0到\(n\)（\(n\)為物品總數(shù)）；

-第二維\(j\)表示背包當前容量，范圍從0到\(C\)。

狀態(tài)初始化：

-當沒有物品可選時（\(i=0\)），無論背包容量如何，最大價值都為0，即：

\[dp[0][j]=0,\quad\forallj\in[0,C]\]

-當背包容量為0時（\(j=0\)），無法放入任何物品，最大價值也為0，即：

\[dp[i][0]=0,\quad\foralli\in[1,n]\]

（三）狀態(tài)轉(zhuǎn)移方程詳細推導

狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃的核心，它描述了如何從子問題的解推導出原問題的解。對于0/1背包問題，狀態(tài)轉(zhuǎn)移方程如下：

\[dp[i][j]=\max\{dp[i-1][j],\quaddp[i-1][j-w[i]]+v[i]\}\]

含義解釋：

1.不選擇第\(i\)件物品：此時最大價值等于前\(i-1\)件物品在容量為\(j\)時的最大價值，即：

\[dp[i-1][j]\]

2.選擇第\(i\)件物品：前提是背包剩余容量\(j\)足夠放入第\(i\)件物品（即\(j\geqw[i]\)），此時最大價值等于：

-前\(i-1\)件物品在容量為\(j-w[i]\)時的最大價值，加上第\(i\)件物品的價值\(v[i]\)，即：

\[dp[i-1][j-w[i]]+v[i]\]

3.綜合選擇：在第\(i\)件物品可選的情況下，選擇兩種方案的較大值作為當前狀態(tài)的最優(yōu)解。

特殊情況處理：

-若當前背包容量\(j\)小于第\(i\)件物品的重量\(w[i]\)，則無法選擇該物品，此時：

\[dp[i][j]=dp[i-1][j]\]

（四）計算過程分步驟詳解

動態(tài)規(guī)劃的求解過程可分為兩種方式：自底向上（迭代）和自頂向下（遞歸+記憶化）。以下是自底向上的計算步驟：

1.初始化DP表格

創(chuàng)建二維數(shù)組\(dp[n+1][C+1]\)，所有元素初始為0。

2.填充DP表格

按物品編號和背包容量順序，逐行逐列計算\(dp[i][j]\)：

-外層循環(huán)：遍歷物品編號\(i\)從1到\(n\)；

-內(nèi)層循環(huán)：遍歷背包容量\(j\)從1到\(C\)；

-在每一步，根據(jù)狀態(tài)轉(zhuǎn)移方程計算\(dp[i][j]\)。

示例計算：

以背包容量\(C=5\)，物品信息為\[w=[2,3,4],v=[3,4,5]\]為例：

|物品\(i\)|容量\(j\)|\(dp[i][j]\)計算過程|最終\(dp[i][j]\)|

|-----------|-----------|-------------------------------------------------------------------------------------|------------------|

|0|0-5|初始化為0|0|

|1|0|\(dp[0][0]=0\)|0|

|1|1|\(dp[0][1]=0\)|0|

|1|2|\(\max(dp[0][2],dp[0][0]+v[1])=\max(0,0+3)=3\)|3|

|1|3|\(\max(dp[0][3],dp[0][0]+v[1])=\max(0,0+3)=3\)|3|

|1|4|\(\max(dp[0][4],dp[0][1]+v[1])=\max(0,0+3)=3\)|3|

|1|5|\(\max(dp[0][5],dp[0][2]+v[1])=\max(0,0+3)=3\)|3|

|2|0|\(dp[0][0]=0\)|0|

|2|1|\(\max(dp[1][1],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|2|\(\max(dp[1][2],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|3|\(\max(dp[1][3],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|4|\(\max(dp[1][4],dp[1][1]+v[2])=\max(0,4+4)=8\)|8|

|2|5|\(\max(dp[1][5],dp[1][2]+v[2])=\max(0,4+4)=8\)|8|

|3|0|\(dp[0][0]=0\)|0|

|3|1|\(\max(dp[2][1],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|2|\(\max(dp[2][2],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|3|\(\max(dp[2][3],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|4|\(\max(dp[2][4],dp[2][1]+v[3])=\max(0,5+5)=10\)|10|

|3|5|\(\max(dp[2][5],dp[2][2]+v[3])=\max(0,5+5)=10\)|10|

3.提取最終結果

最大價值存儲在\(dp[n][C]\)中，即\(dp[3][5]=10\)。

（五）最優(yōu)解路徑回溯

動態(tài)規(guī)劃不僅計算最大價值，還能通過回溯找到具體的選擇方案?；厮莶襟E如下：

1.從\(dp[n][C]\)開始，比較\(dp[i][j]\)與\(dp[i-1][j]\)：

-若\(dp[i][j]=dp[i-1][j]\)，則第\(i\)件物品未被選擇；

-若\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，則第\(i\)件物品被選擇，記錄該物品。

2.重復上述步驟，直到\(i=0\)。

示例回溯：

-\(dp[3][5]=10\)，比較\(dp[3][5]\)與\(dp[2][5]\)：

-\(10\neq8\)，說明第3件物品被選擇，價值為5；

-更新剩余容量：\(j=5-4=1\)；

-\(dp[2][1]=5\)，比較\(dp[2][1]\)與\(dp[1][1]\)：

-\(5\neq4\)，說明第2件物品被選擇，價值為4；

-更新剩余容量：\(j=1-3=-2\)（不合法，停止）；

-最終選擇的物品為第2和第3件。

六、動態(tài)規(guī)劃優(yōu)化技巧

為了提高效率，可以優(yōu)化動態(tài)規(guī)劃的實現(xiàn)：

（一）空間優(yōu)化

0/1背包問題中，狀態(tài)轉(zhuǎn)移僅依賴于前一行的數(shù)據(jù)，因此可使用一維數(shù)組代替二維數(shù)組，降低空間復雜度：

-初始化一個長度為\(C+1\)的數(shù)組，按行順序更新。

示例代碼片段（偽代碼）：

int[]dp=newint[C+1];

for(inti=0;i<n;i++){

for(intj=C;j>=w[i];j--){

dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);

}

}

（二）剪枝優(yōu)化

在遞歸求解時，可通過剪枝減少不必要的計算：

-若當前選擇導致剩余容量無法達到更大價值，則跳過該選擇。

七、其他約束優(yōu)化問題類比

動態(tài)規(guī)劃的應用不僅限于背包問題，其他約束優(yōu)化問題也可類似建模：

（一）生產(chǎn)調(diào)度問題

-目標：在設備資源約束下，最小化生產(chǎn)時間或最大化產(chǎn)量；

-約束：設備工作時間、物料限制；

-動態(tài)規(guī)劃解法：

1.定義狀態(tài)：\(dp[i][j]\)表示前\(i\)個任務在資源\(j\)下的最優(yōu)時間；

2.轉(zhuǎn)移方程：考慮每個任務對資源的影響；

3.回溯：找出最優(yōu)任務順序。

（二）路徑規(guī)劃問題

-目標：在圖網(wǎng)絡中尋找最短或最長路徑，如旅行商問題（TSP）；

-約束：路徑長度、節(jié)點訪問次數(shù)；

-動態(tài)規(guī)劃解法：

-使用狀態(tài)表示已訪問節(jié)點集合和當前節(jié)點；

-轉(zhuǎn)移方程：選擇下一個未訪問節(jié)點，更新路徑成本。

八、總結與擴展

動態(tài)規(guī)劃通過將復雜問題分解為子問題，并利用最優(yōu)子結構和重疊子問題特性，高效解決約束優(yōu)化問題。關鍵步驟包括：

1.定義狀態(tài)表示；

2.建立狀態(tài)轉(zhuǎn)移方程；

3.初始化邊界條件；

4.計算最優(yōu)解并回溯。

擴展方向：

-多重背包問題：物品可多次選擇，轉(zhuǎn)移方程需調(diào)整；

-完全背包問題：物品可無限選擇，可優(yōu)化為一維DP；

-0/1背包的貪心擴展：部分場景可用貪心算法近似求解，但無法保證全局最優(yōu)。

一、引言

動態(tài)規(guī)劃（DynamicProgramming,DP）是一種解決復雜優(yōu)化問題的算法思想，通過將問題分解為子問題并存儲子問題的解（記憶化或自底向上）來避免重復計算，從而提高效率。約束優(yōu)化問題是指在優(yōu)化目標的同時，需要滿足一系列約束條件的數(shù)學問題。動態(tài)規(guī)劃在處理具有遞歸結構和重疊子問題時具有顯著優(yōu)勢，特別適用于資源分配、路徑規(guī)劃、生產(chǎn)調(diào)度等場景。

二、動態(tài)規(guī)劃的基本原理

動態(tài)規(guī)劃的核心思想是將原問題分解為多個子問題，并通過以下兩個關鍵特性實現(xiàn)優(yōu)化：

（一）最優(yōu)子結構

若問題的最優(yōu)解包含子問題的最優(yōu)解，則該問題具有最優(yōu)子結構。例如，最短路徑問題中，從起點到終點的最短路徑包含從中間節(jié)點到終點的最短路徑。

（二）重疊子問題

在遞歸求解過程中，多個子問題可能被重復計算。動態(tài)規(guī)劃通過存儲子問題的解（如使用數(shù)組或哈希表）來避免重復計算，降低時間復雜度。

三、動態(tài)規(guī)劃在約束優(yōu)化問題中的應用

動態(tài)規(guī)劃適用于具有以下特征的約束優(yōu)化問題：

（一）離散決策問題

在每一步選擇有限個決策，且決策序列決定最終結果。例如，背包問題中，每次只能選擇放入或不放入一個物品。

（二）可分解為子問題

原問題可表示為多個子問題的組合，且子問題之間相互獨立。例如，斐波那契數(shù)列的計算可分解為多個小的斐波那契數(shù)列計算。

（三）狀態(tài)轉(zhuǎn)移方程

\[

\text{狀態(tài)方程：}\quadS(i)=\min/max\{\text{決策}\times\text{收益}+S(i-1)\}

\]

其中，\(S(i)\)表示第\(i\)步的最優(yōu)狀態(tài)，決策影響當前收益和后續(xù)狀態(tài)。

四、應用步驟

（一）定義狀態(tài)

明確問題的狀態(tài)表示，通常用數(shù)組或哈希表存儲子問題的解。例如，在背包問題中，狀態(tài)表示為當前容量下的最大價值。

（二）確定狀態(tài)轉(zhuǎn)移方程

根據(jù)問題特性建立狀態(tài)轉(zhuǎn)移方程，確保子問題解的遞推關系正確。例如：

-背包問題：

\[

\text{dp}[i][j]=\max\{\text{dp}[i-1][j],\text{dp}[i-1][j-w[i]]+v[i]\}

\]

其中，\(w[i]\)為物品重量，\(v[i]\)為物品價值。

（三）初始化邊界條件

設定初始狀態(tài)，通常為第0步或第0容量時的解。例如：

\[

\text{dp}[0][j]=0,\quad\text{dp}[i][0]=0

\]

（四）計算最優(yōu)解

1.自底向上：從第1步到最終步逐層計算；

2.自頂向下：使用遞歸并存儲已計算結果。

五、示例：0/1背包問題

以0/1背包問題為例，說明動態(tài)規(guī)劃的應用：

（一）問題描述

給定物品重量和價值，以及背包容量，選擇物品放入背包使總價值最大，且總重量不超過背包容量。

（二）狀態(tài)定義

-狀態(tài)：\(dp[i][j]\)表示前\(i\)件物品在容量為\(j\)時的最大價值。

（三）狀態(tài)轉(zhuǎn)移方程

\[

dp[i][j]=\max\{dp[i-1][j],\quaddp[i-1][j-w[i]]+v[i]\}

\]

其中，若\(j<w[i]\)，則\(dp[i][j]=dp[i-1][j]\)。

（四）計算過程

1.初始化：

-\(dp[0][j]=0\)（未選擇物品時價值為0）；

-\(dp[i][0]=0\)（容量為0時價值為0）。

2.逐行計算：

-對于每個物品，更新當前容量下的最大價值。

（五）結果提取

最終解為\(dp[n][C]\)，其中\(zhòng)(n\)為物品數(shù)量，\(C\)為背包容量。

六、總結

動態(tài)規(guī)劃通過分解子問題、存儲解和建立狀態(tài)轉(zhuǎn)移方程，高效解決約束優(yōu)化問題。其應用的關鍵在于識別問題的最優(yōu)子結構和重疊子問題，并設計合理的狀態(tài)表示和轉(zhuǎn)移方程。通過以上步驟，可推廣至其他約束優(yōu)化問題，如資源分配、路徑規(guī)劃等。

五、示例：0/1背包問題（續(xù)）

（一）問題描述詳細闡述

0/1背包問題是最經(jīng)典的動態(tài)規(guī)劃應用之一，其約束條件清晰，適合通過動態(tài)規(guī)劃進行建模和求解。問題描述如下：

-輸入：

-一系列物品，每個物品有確定的重量（\(w[i]\)）和價值（\(v[i]\)）；

-背包的最大承載容量（\(C\)）。

-輸出：

-將哪些物品放入背包，使背包內(nèi)物品總價值最大，且總重量不超過背包容量。

-注意：每個物品只能選擇放入或不放入，不能分割。

示例：

假設有3件物品，重量分別為\[2,3,4\]，價值分別為\[3,4,5\]，背包容量為\(C=5\)。目標是選擇物品組合使總價值最大。

（二）狀態(tài)定義進一步說明

在動態(tài)規(guī)劃中，狀態(tài)表示為決策過程中的某個階段的最優(yōu)解。對于0/1背包問題，狀態(tài)定義如下：

-狀態(tài)表示：

-\(dp[i][j]\)表示從前\(i\)件物品中選取，且背包剩余容量為\(j\)時的最大價值。

-狀態(tài)維度：

-第一維\(i\)表示物品編號，范圍從0到\(n\)（\(n\)為物品總數(shù)）；

-第二維\(j\)表示背包當前容量，范圍從0到\(C\)。

狀態(tài)初始化：

-當沒有物品可選時（\(i=0\)），無論背包容量如何，最大價值都為0，即：

\[dp[0][j]=0,\quad\forallj\in[0,C]\]

-當背包容量為0時（\(j=0\)），無法放入任何物品，最大價值也為0，即：

\[dp[i][0]=0,\quad\foralli\in[1,n]\]

（三）狀態(tài)轉(zhuǎn)移方程詳細推導

狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃的核心，它描述了如何從子問題的解推導出原問題的解。對于0/1背包問題，狀態(tài)轉(zhuǎn)移方程如下：

\[dp[i][j]=\max\{dp[i-1][j],\quaddp[i-1][j-w[i]]+v[i]\}\]

含義解釋：

1.不選擇第\(i\)件物品：此時最大價值等于前\(i-1\)件物品在容量為\(j\)時的最大價值，即：

\[dp[i-1][j]\]

2.選擇第\(i\)件物品：前提是背包剩余容量\(j\)足夠放入第\(i\)件物品（即\(j\geqw[i]\)），此時最大價值等于：

-前\(i-1\)件物品在容量為\(j-w[i]\)時的最大價值，加上第\(i\)件物品的價值\(v[i]\)，即：

\[dp[i-1][j-w[i]]+v[i]\]

3.綜合選擇：在第\(i\)件物品可選的情況下，選擇兩種方案的較大值作為當前狀態(tài)的最優(yōu)解。

特殊情況處理：

-若當前背包容量\(j\)小于第\(i\)件物品的重量\(w[i]\)，則無法選擇該物品，此時：

\[dp[i][j]=dp[i-1][j]\]

（四）計算過程分步驟詳解

動態(tài)規(guī)劃的求解過程可分為兩種方式：自底向上（迭代）和自頂向下（遞歸+記憶化）。以下是自底向上的計算步驟：

1.初始化DP表格

創(chuàng)建二維數(shù)組\(dp[n+1][C+1]\)，所有元素初始為0。

2.填充DP表格

按物品編號和背包容量順序，逐行逐列計算\(dp[i][j]\)：

-外層循環(huán)：遍歷物品編號\(i\)從1到\(n\)；

-內(nèi)層循環(huán)：遍歷背包容量\(j\)從1到\(C\)；

-在每一步，根據(jù)狀態(tài)轉(zhuǎn)移方程計算\(dp[i][j]\)。

示例計算：

以背包容量\(C=5\)，物品信息為\[w=[2,3,4],v=[3,4,5]\]為例：

|物品\(i\)|容量\(j\)|\(dp[i][j]\)計算過程|最終\(dp[i][j]\)|

|-----------|-----------|-------------------------------------------------------------------------------------|------------------|

|0|0-5|初始化為0|0|

|1|0|\(dp[0][0]=0\)|0|

|1|1|\(dp[0][1]=0\)|0|

|1|2|\(\max(dp[0][2],dp[0][0]+v[1])=\max(0,0+3)=3\)|3|

|1|3|\(\max(dp[0][3],dp[0][0]+v[1])=\max(0,0+3)=3\)|3|

|1|4|\(\max(dp[0][4],dp[0][1]+v[1])=\max(0,0+3)=3\)|3|

|1|5|\(\max(dp[0][5],dp[0][2]+v[1])=\max(0,0+3)=3\)|3|

|2|0|\(dp[0][0]=0\)|0|

|2|1|\(\max(dp[1][1],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|2|\(\max(dp[1][2],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|3|\(\max(dp[1][3],dp[1][0]+v[2])=\max(0,0+4)=4\)|4|

|2|4|\(\max(dp[1][4],dp[1][1]+v[2])=\max(0,4+4)=8\)|8|

|2|5|\(\max(dp[1][5],dp[1][2]+v[2])=\max(0,4+4)=8\)|8|

|3|0|\(dp[0][0]=0\)|0|

|3|1|\(\max(dp[2][1],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|2|\(\max(dp[2][2],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|3|\(\max(dp[2][3],dp[2][0]+v[3])=\max(0,0+5)=5\)|5|

|3|4|\(\max(dp[2][4],dp[2][1]+v[3])=\max(0,5+5)=10\)|10|

|3|5|\(\max(dp[2][5],dp[2][2]+v[3])=\max(0,5