一、總體說明
最近在備戰(zhàn)藍(lán)橋杯，感覺藍(lán)橋杯很多題目都可以嘗試用暴力搜索，暴力枚舉的方法嘗試得出最終的結(jié)果，但是暴力的方式效率并不是很高，而且容易超時。在以前學(xué)回溯算法的時候，也是一臉懵，不理解IndexStart到底什么意思，不知道如何去找參數(shù)和遞歸邏輯，好在通過慢慢的學(xué)習(xí)和做題，逐漸對這類算法有了進(jìn)一步的認(rèn)識，下次可以單獨出一期講回溯算法。
本次博客主要講述的是動態(tài)規(guī)劃算法，也就是那個明明知道什么叫動態(tài)，什么叫規(guī)劃，連起來就不知道它到底是什么的算法了。其實本人也還在一個在學(xué)習(xí)的過程，但通過幾天的學(xué)習(xí)和思考，逐漸對DP有了一個新的認(rèn)識，以下我將慢慢來進(jìn)行說明我對DP的一個學(xué)習(xí)認(rèn)識過程。
二、動態(tài)規(guī)劃的概念
本人習(xí)慣于對任何問題，無論是學(xué)高數(shù)還是大物，甚至是數(shù)據(jù)結(jié)構(gòu)與算法，都首先從其最初始的定義開始。那么什么叫動態(tài)規(guī)劃呢？
動態(tài)規(guī)劃（Dynamic Programming，簡稱DP）是一種解決多階段決策問題的數(shù)學(xué)優(yōu)化方法。它將原問題分解成若干個子問題，通過解決子問題只需解決一次并將結(jié)果保存下來，從而避免了重復(fù)計算，提高了算法效率?？偟膩碇v，動態(tài)規(guī)劃算法使用時，這個問題得具備兩個要素：1.重疊子問題2.最優(yōu)子結(jié)構(gòu)。
三、具體示例
大體來說，判斷一個題目適不適合動態(tài)規(guī)劃，就得去嘗試尋找對于這個題目來說，他存不存在最優(yōu)子結(jié)構(gòu)和重疊子問題。如果確實存在，那么如何去嘗試用DP算法去解決這個問題呢？接下來跟著我的思路，去嘗試看三個DP的問題，相信你會有更多的收獲。
3.1 找出連續(xù)子序列的最大和
筆者是通過一個視頻認(rèn)識這道題的，這個視頻在嗶站，在搜索框中輸入動態(tài)規(guī)劃，第一個視頻就是它。視頻鏈接在這。10分鐘徹底搞懂“動態(tài)規(guī)劃”算法_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV1AB4y1w7eT/?spm_id_from=333.337.search-card.all.click&vd_source=09d0a5241128639946dcdfb5bf184df2感興趣的小伙伴可以去看看，相信會對你有所幫助。
這道題目是這樣說的，給定一個一維數(shù)組，嘗試找出這個一維數(shù)組的連續(xù)子序列的最大和。如給出一維數(shù)組[3，-4，2，-1，2，6，-5，4]，這個一維數(shù)組的最大連續(xù)子序列和為2+(-1)+2+6=9。
那么怎么去做這道題目呢？想開始我拿到這道題目也是一臉懵。一直反復(fù)在腦子里面思考“連續(xù)子序列的最大和，連續(xù)子序列的最大和，連續(xù)子序列的最大和”。但是重點在于這個嘛？重點在于你不要被他所謂的標(biāo)簽給束縛了，有人告訴你這道題可以用動態(tài)規(guī)劃去解決，你就反反復(fù)復(fù)地去嘗試用動態(tài)規(guī)劃的思想去解決。首先嘗試去定義一個DP數(shù)組，確定這個DP數(shù)組的意思是什么，然后去找到狀態(tài)轉(zhuǎn)移方程，然后定義初始化的條件？？？？是這樣做的嘛？顯然不是。
對于這道題，我認(rèn)為最好的方式是不要認(rèn)為他可以用DP去解決，假裝你自己并不知道這道題可以用DP，你甚至不知道這道題怎么去解決。到底能用數(shù)據(jù)結(jié)構(gòu)或者算法中的哪一個去解決，你自己完全不知道。你首先第一步需要做的事情是去分析。這道題目說的是連續(xù)子序列，那么我們就從最開始的3開始，3+(-4)，3+(-4)+2，3+(-4)+2+(-1).........，一直往后，然后從-4開始，從2開始，你發(fā)現(xiàn)了什么？在算3+(-4)+2+(-1)的時候，我是不是算過了3+(-4)，我從2開始的話是不是算過了2+(-1)？所以，你發(fā)現(xiàn)了什么？一個很長的連續(xù)序列長串，他確確實實是由一個個連續(xù)序列短串加起來得到的，所以是不是存在子結(jié)構(gòu)？顯然，長串的最優(yōu)解也是由子串的最優(yōu)解得出，也就是說是存在最優(yōu)子結(jié)構(gòu)，不用多說，必然也是一個重疊子問題。那么說明了什么，這道題可以用DP的思想來進(jìn)行解決。
那么DP首先實現(xiàn)三部曲，第一確定你的DP數(shù)組的含義，其次找到狀態(tài)轉(zhuǎn)移方程，接著初始化，最后進(jìn)行相應(yīng)的操作，實現(xiàn)整個算法思路和過程就OK了。那么問題來了，DP數(shù)組的含義我們怎么去確定呢？我覺得最簡單的方式就是，他要求什么，我就設(shè)什么。既然這道題目讓我求的就是子序列的和，我就定義這個dp數(shù)組的值就是子序列的和。那么怎么去確定這個dp數(shù)組是一維還是二維呢，也就是具體的含義是什么？這就得看你上面的分析了，第一個重點在于你的連續(xù)子序列從哪里開始，也就是數(shù)組的索引值是什么，其次在于你的連續(xù)子序列的長度是什么，所以這個dp就是一個二維數(shù)組，因為你的這個子序列的值和這兩個因素有關(guān)。那么我們就可以定義dp[i][j]的含義為從數(shù)組的索引值為i處開始的長度為j的連續(xù)子序列的和。
那么問題來了，這個狀態(tài)轉(zhuǎn)移方程式什么呢？其實你加以分析一下，你要分析，要去動手，不然永遠(yuǎn)憑腦子去想的話永遠(yuǎn)都想不出來。dp[i][j]表示數(shù)組的索引值為i處開始的長度為j的連續(xù)子序列的和，那么dp[i-1][j]等于什么呢？dp[i][j-1]的含義是什么？索引值為i處開始的長度和j-1的連續(xù)子序列的和，所以dp[i][j]=dp[i][j-1]+arr[i+j-1]。這里把原數(shù)組定義為arr。
dp數(shù)組定義和狀態(tài)轉(zhuǎn)移方程已經(jīng)寫完了，那么接下去就是去實現(xiàn)dp數(shù)組的初始化。你可以將dp數(shù)組都初始化為0，也可以dp[0][1]=arr[0]都可以。這其實是和你的狀態(tài)轉(zhuǎn)移方程有一定的聯(lián)系，可以多思考思考，初始化很重要。
代碼的具體實現(xiàn)如下：
#include <iostream>
#include <vector>
using namespace std;
int dp[50][50];
vector<int> arr;
int main()
{
int n, result;
result = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
arr.push_back(num);
}
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= n - i; j++)
{
dp[i][j] = dp[i][j - 1] + arr[j + i - 1];
if (dp[i][j] > result)
{
result = dp[i][j];
}
}
}
cout << result << endl;
return 0;
}運行結(jié)果如下：
3.2 數(shù)組分割
我們再來看一道藍(lán)橋杯真題。一樣的，我們假裝不知道這題目可以用動態(tài)規(guī)劃來解決，通過自己的分析和探索，來看看這道題的原理和內(nèi)層邏輯是什么，可不可以用動態(tài)規(guī)劃去實現(xiàn)，如果可以用動態(tài)規(guī)劃去實現(xiàn)，我們該怎么去實現(xiàn)？
具體題目如下：
題目鏈接為用戶登錄https://www.lanqiao.cn/problems/3535/learning/
遇到任何題目，第一步最重要的不是看他到底是用什么算法去解決，最重要的點在于自己去分析。分析問題，看看這道題適合用什么方式去解決。所以，讓我們開始動手去做，去嘗試，看看怎么具體解決這個問題。
首先理解題目意思，先不管有幾組數(shù)據(jù)，我們先嘗試一組數(shù)據(jù)。給出一個數(shù)組，隨便在這個數(shù)組里面選擇數(shù)字，使數(shù)字之和為一個偶數(shù)，有多少種不同的選擇方式。當(dāng)然，需要保證S1、S2都為偶數(shù)，那么第一，整個數(shù)組的和是不是得為偶數(shù)。這就出現(xiàn)了第一個判斷的條件了，腦子就可以開始寫if判斷了。
接下來，繼續(xù)去思考，假如說對于一個數(shù)組[1,3,5,7,12,6,8]。我需要隨便找數(shù)字，讓他的和為偶數(shù)，我該怎么去找呢？可以選擇1，可以選擇3，可以選擇5，甚至是7，這就顯的很雜亂無章。如果我選擇了1+3+5，那么后面再遇到1+3+5+7的時候，我是不是可以用前面已經(jīng)算好的1+3+5得到的結(jié)果，再去加7呢？當(dāng)然可以，那么就往這個方向去思考，存在子結(jié)構(gòu)，重疊子問題，可以嘗試。那么dp數(shù)組的定義就是所選數(shù)字之和，但是有個新問題，和找連續(xù)子序列的最大和這個問題不一樣，他是一個連續(xù)的子序列，我這里是不連續(xù)的，是可以隨機取的，是無序的，這里的i，j就無法定義，或者說定義了，你也沒法找到狀態(tài)轉(zhuǎn)移方程。所以這道題，和以前寫過的都不一樣。
那么我們該怎么去思考呢？嘗試從問題的結(jié)果出發(fā)，去尋找問題。這道題的問題是什么？是讓我們?nèi)デ筮x擇的R1有多少種可能的情況。好，那我們這樣來思考，既然這個數(shù)組他很長，那么我們就選擇其中i個數(shù)吧，反正i小于等于這個數(shù)組的長度。從i個數(shù)中隨便選擇數(shù)，使選擇的數(shù)之和為偶數(shù)的方式有x種，那你再去思考一下，我這時候再從整個數(shù)組中（除去那已經(jīng)拿出的i個數(shù)）拿出一個數(shù)，對于這個數(shù)來說，是不是有兩種可能，第一種，選擇這個數(shù)，第二種，不選擇這個數(shù)。那如果你這個數(shù)他是偶數(shù)，前面i個數(shù)中隨便選擇的數(shù)之和也為偶數(shù)，偶數(shù)+偶數(shù)當(dāng)然是符號條件的，所以你把這個數(shù)加入i個數(shù)中，那么在i+1個數(shù)中任意選擇數(shù)，使之和為偶數(shù)的情況有多少種？思考下，沒錯，就是2x種。同樣，如果是奇數(shù)，可以自行按著這個思路進(jìn)行思考下去，我就不再贅述。
那么思考完了之后，你就會發(fā)現(xiàn)，這不是一個動態(tài)規(guī)劃的思路嘛？存在最優(yōu)子結(jié)構(gòu)，也是一個最優(yōu)子問題，還有相應(yīng)的狀態(tài)轉(zhuǎn)移方程，所以就是一個DP問題。
那么開始吧，我們嘗試去寫代碼實現(xiàn)，具體代碼如下：
#include <iostream>
#include <vector>
using namespace std;
//dp[i][0] 從數(shù)組前面i個數(shù)任意組合，得到結(jié)果和為偶數(shù)記為0，dp的值為從數(shù)組前面i個數(shù)任意組合，得到結(jié)果和為偶數(shù)的子集個數(shù)
//dp[i][1] 從數(shù)組前面i個數(shù)任意組合，得到結(jié)果和為奇數(shù)記為1，dp的值為從數(shù)組前面i個數(shù)任意組合，得到結(jié)果和為奇數(shù)的子集個數(shù)
//如果arr[i]為偶數(shù)，那么dp[i+1][0]=dp[i][0]*2
//如果arr[i]為奇數(shù)，那么dp[i+1][0]=dp[i][0]+dp[i][1]
long long mod = 1e9 + 7;
int main()
{
int n, q;
cin >> n;
q = 0;
vector<int> storge(n);
while ( q < n)
{
int m, sum;
cin >> m;
vector<int> arr;
sum = 0;
for (int i = 0; i < m; i++)
{
int num;
cin >> num;
sum += num;
arr.push_back(num);
}
if (sum % 2 == 0)
{
int dp[1010][2];
dp[0][0] = 1;
dp[0][1] = 0;
for (int i = 1; i <= m; i++)
{
if (arr[i-1] % 2 == 0)
{
dp[i][0] = 2 * (dp[i - 1][0]) % mod;
dp[i][1] = 2 * (dp[i - 1][0]) % mod;
}
else
{
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
}
}
storge[q] = dp[m][0];
}
else
{
storge[q] = 0;
}
q += 1;
}
for (int i = 0; i < q; i++)
{
cout << storge[i] << endl;
}
return 0;
}?測試用例運行效果截圖：
藍(lán)橋測試用例只通過了20%，最近一直苦惱于樣式用例好像都能通過，但是一旦測試用例，就有一部分能過，或者都不能過這種。有知道為什么的小伙伴也可以寫在評論區(qū)或者私信我，告訴我一下怎么解決這個問題。（我覺得我寫的這個代碼的思路是沒有問題的。）
藍(lán)橋測試截圖：
3.3 保險箱問題
題目鏈接在這
用戶登錄https://www.lanqiao.cn/problems/3545/learning/首先一樣的，先假裝不知道這道題能用什么方式去解決，去動腦子，去思考，嘗試對問題從最基礎(chǔ)的地方開始剖析。
一個保險箱有n個數(shù)字，x為初始輸入數(shù)字，y為我們需要變成的數(shù)字。根據(jù)題目的意思，實際上也就是說anan-1an-2......a0其實也就是為an*pow（10，n-1）+.....a0，所以第一個性質(zhì)，無所謂你從哪個數(shù)字開始進(jìn)行調(diào)整，可以是an，也可以是an-1，你隨便調(diào)整。比如對于所給樣例，輸入12349，得到54321，你可以選擇從1開始先調(diào)整到5，也可從2開始調(diào)整到4，依次類推都行。
既然怎么調(diào)整都行，我們盡量做到有序，那么要保證有序，可以從左到右，或者從右往左。假如從左往右去進(jìn)行調(diào)整，思考一個問題，對于一個數(shù)，比如從9變成1，有兩種可能，第一種我直接給9+2，是不是可以將這個位上的數(shù)變成1，或者說我從9直接-8也能變成1，反正不管怎么樣，我要將x上的某一位變成y上的某一位，無非就是這兩種操作。既然如此如果從左往右開始進(jìn)行，如果對于第二位你進(jìn)行了進(jìn)位操作，勢必會影響到第一位，那么第一位剛處理完豈不是白處理了。但是反過來，你從末尾開始從右往左進(jìn)行調(diào)整，你可以發(fā)現(xiàn)，我只要調(diào)整好了這一位，影響的是前一位，但是前一位并沒有進(jìn)行調(diào)整過，因此，我們選擇從右開始向左調(diào)整。
所以經(jīng)過分析，我覺得可以用暴力搜索的方式去嘗試解決這個問題，事實上遞歸的深度也就是整個數(shù)字的個數(shù)n，每一次操作，都有兩種可能，要么進(jìn)位/退位，要么直接在對應(yīng)位置上進(jìn)行+/-的操作。
以下是我實現(xiàn)的dfs的代碼：
#include <iostream>
#include <string>
using namespace std;
int n;//數(shù)字位數(shù)
string x, y;//x為輸入數(shù)字，y為目標(biāo)數(shù)字
int arr[50];//1代表該數(shù)字直接加/減，2代表該數(shù)字進(jìn)位/退位
int ninef(int a, int b, int flag)
{
int res;
//flag為1，說明直接進(jìn)行加/減
if (a > b && flag == 1)
{
res = a - b;
return res;
}
//flag為1，進(jìn)行退位/進(jìn)位操作
if (a > b && flag == 2)
{
res = 10 + b - a;
return res;
}
if (a < b && flag == 1)
{
res = b - a;
return res;
}
if (a < b && flag == 2)
{
res = 10 + a - b;
return res;
}
}
void dfs(int startIndex,int result, int& max_num)
{
if (startIndex < 0)
{
if (result < max_num)
{
max_num = result;
}
return;
}
int a = x[startIndex] - '0';
int b = y[startIndex] - '0';
//遞歸邏輯
if (a > b)
{
arr[startIndex] = 1;
result += ninef(a, b, 1);
dfs(startIndex - 1, result, max_num);
arr[startIndex] = 0;
result -= ninef(a, b, 1);
arr[startIndex] = 2;
result += ninef(a, b, 2);
if (startIndex != 0)
{
x[startIndex - 1] += 1;
}
dfs(startIndex - 1, result, max_num);
arr[startIndex] = 0;
result -= ninef(a, b, 2);
if (startIndex != 0)
{
x[startIndex - 1] -= 1;
}
}
if (a < b)
{
arr[startIndex] = 1;
result += ninef(a, b, 1);
dfs(startIndex - 1, result, max_num);
arr[startIndex] = 0;
result -= ninef(a, b, 1);
arr[startIndex] = 2;
result += ninef(a, b, 2);
if (startIndex != 0)
{
x[startIndex - 1] -= 1;
}
dfs(startIndex - 1, result, max_num);
arr[startIndex] = 0;
result -= ninef(a, b, 2);
if (startIndex != 0)
{
x[startIndex - 1] += 1;
}
}
if (a == b)
{
dfs(startIndex - 1, result, max_num);
}
}
int main()
{
cin >> n;
cin >> x >> y;
int max_num = 100000;
int result = 0;
dfs(n - 1, result, max_num);
cout << max_num << endl;
return 0;
}運行樣例如下：
樣例運行沒問題，再藍(lán)橋官方運行的話只通過了百分之二十的樣例
既然如此，通過上述分析，其實不難發(fā)現(xiàn)一個DP的思想在里面，且聽我慢慢道來。
我以簡單一點的實例進(jìn)行說明。
n=3 ，x=129 ，y=531，結(jié)合上述分析，不難畫出如下圖所示的樹狀結(jié)構(gòu)圖
剩下的節(jié)點可以自行畫完。整個最小方案就是9+2，然后3不變，最后1變5，最小方案為6。其實對每個結(jié)點來說，無非是兩種情況，到底是+/-得來的，還是進(jìn)位/退位得來的呢？這里以x和y的從左往右數(shù)的第二位來說明吧。假設(shè)現(xiàn)狀9已經(jīng)變?yōu)榱?，那么9怎么樣變?yōu)?呢？是+還是減？+了必然會影響他的前一位，減了并不影響前一位，所以我第二位有幾種變來的方式？取決于上一位怎么變化。同時，通過樹結(jié)構(gòu)不難發(fā)現(xiàn)，整個最優(yōu)解其實就在一條路徑上，你會發(fā)現(xiàn)，整體的最優(yōu)解，其實也就是每一步的最優(yōu)方案。對于9而言，總體最優(yōu)的方案就是9+2，而實際單獨拿出9來說，其最優(yōu)解也是對9+2，變成1。那么存在最優(yōu)子結(jié)構(gòu)，存在重疊子問題，又何嘗不是一個DP問題呢。
那么既然整道題目是一個DP問題，首先得確定DP數(shù)組的含義到底是什么?；氐綐浣Y(jié)構(gòu)，觀察每一個結(jié)點，DP問題不就是找到前后之間的聯(lián)系嘛，試著去找一下。第一個節(jié)點有兩種方式變?yōu)槟繕?biāo)節(jié)點，但實際上他自己如何變會影響到下一節(jié)點，那么這就是前后之間的關(guān)系。那么就可以定義了，DP[i][j]為目標(biāo)為i的節(jié)點通過j的方式得到，而j有什么可能，要么+，要么-，所以j的值可為0/1。具體代碼如下：
#include<bits/stdc++.h>
using namespace std;
int n;
int x[100010];//存放輸入:1 2 3 4 9
int y[100010];//存放答案:5 4 3 2 1
int dp[100010][2];//dp[i,j]表示（從后向前數(shù)）第i位達(dá)到了目標(biāo)，且第i位是靠+實現(xiàn)的(y==0)或者第i位是靠-實現(xiàn)的（y==1）
void fun()
{
dp[0][0] = (y[0]-x[0]+10)%10;//9加到2
dp[0][1] = (x[0]-y[0]+10)%10;//9減到2
for( int i=1;i<=n-1;i++ )//以i=1為例： 無非就是當(dāng)前是加減，上一位是加減，四種排列組合狀態(tài)
{
dp[i][0] = min( (y[i] - x[i] - (y[i-1]<x[i-1]) +10 )%10 + dp[i-1][0],//(2-4-(1<9)+10)%10+2 = 9：9先加到1，5再加到2
(y[i] - x[i] + (y[i-1]>x[i-1]) +10 )%10 + dp[i-1][1]);//(2-4+(1>9)+10)%10+7 = 16:9先減到1，4再加到2
dp[i][1] = min( (x[i] - y[i] + (y[i-1]<x[i-1]) +10 )%10 + dp[i-1][0],//(4-2+(1<9)+10)%10+2 = 5: 9先加到1，5再減到2
(x[i] - y[i] - (y[i-1]>x[i-1]) +10 )%10 + dp[i-1][1]);//(4-2-(1>9)-2+10)%10+2 = 10：9先減到1，4再減到2
}
cout<<min( dp[n-1][0],dp[n-1][1] )<<endl;//最終的結(jié)果，可能是加來的，也有可能是減來的。
}
int main()
{
cin>>n;
char c;
for( int i=n-1;i>=0;i-- )
{
cin>>c;
x[i] = c-'0';
}
for( int i=n-1;i>=0;i-- )
{
cin>>c;
y[i] = c-'0';
}
fun();
}四、總結(jié)
動態(tài)規(guī)劃算法的變形有很多，題型有很多，解題的方法也有很多。想要把動態(tài)規(guī)劃算法用的如魚得水，我覺得還是得多刷題目并不斷思考。文章來源：http://www.zghlxwxcb.cn/news/detail-845405.html
學(xué)習(xí)算法時，重點不在于這道題的標(biāo)簽是什么，更重要的在于去思考這道題目的底層邏輯，嘗試去對問題進(jìn)行剖析，而不是停留在用DP或者回溯或者別的算法的公式去套。題目是活的，人也是活的，希望我們都能在不斷解決問題的快樂中繼續(xù)前行。文章來源地址http://www.zghlxwxcb.cn/news/detail-845405.html
到了這里，關(guān)于動態(tài)規(guī)劃（DP）學(xué)習(xí)和思考的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
