?

接觸動(dòng)態(tài)規(guī)劃這么久了，簡(jiǎn)單談一下自己對(duì)動(dòng)態(tài)規(guī)劃的理解。
動(dòng)態(tài)規(guī)劃名字聽(tīng)起來(lái)好像比比較高大上，可是事實(shí)上，人家就是比較高大上。（抖個(gè)機(jī)靈）

剛開(kāi)始接觸動(dòng)態(tài)規(guī)劃的時(shí)候覺(jué)得好可怕，這么復(fù)雜的問(wèn)題我怎么能想的出來(lái)，這樣的問(wèn)題計(jì)算機(jī)怎么能夠解決？

我覺(jué)得動(dòng)態(tài)規(guī)劃不是一種準(zhǔn)確的算法，而是一種思想，一種特殊的搜索思想。這種思想的本質(zhì)是將比較復(fù)雜的搜索問(wèn)題變成一個(gè)遞推題，而遞推公式就是我們常常提到的狀態(tài)轉(zhuǎn)移方程（可能并不準(zhǔn)確，但是我是這樣理解的），或者是說(shuō)將記憶化搜索的遞歸形式寫成了遞推形式。而問(wèn)題的核心就是找到傳說(shuō)中的最優(yōu)子結(jié)構(gòu)和狀態(tài)轉(zhuǎn)移方程。

對(duì)于最優(yōu)子結(jié)構(gòu)，我們要思考儲(chǔ)存狀態(tài)的方式以及特殊的狀態(tài)。這種狀態(tài)一般比較簡(jiǎn)單容易分析。一般是最后一次，因?yàn)樽詈笠淮蔚母蓴_因素比較少，有利于找到問(wèn)題的核心。而通過(guò)對(duì)最后狀態(tài)的分析結(jié)合對(duì)狀態(tài)的儲(chǔ)存方式寫出狀態(tài)轉(zhuǎn)移方程。

除此之外，對(duì)于狀態(tài)的分析還需要一定的貪心的思想。

但是寫出狀態(tài)轉(zhuǎn)移方程并不是結(jié)束，重要的是通過(guò)特殊狀態(tài)的狀態(tài)轉(zhuǎn)移方程推廣到一般情況下。這種推廣方式就是我們的代碼結(jié)構(gòu)。
可是這種推廣也不容易一眼看出來(lái)（除非你已經(jīng)有很多經(jīng)驗(yàn)或者是你做過(guò)比較相似的題），所以我們要從比較簡(jiǎn)單的情況結(jié)合我們的狀態(tài)轉(zhuǎn)移方程進(jìn)行分析，這也是完善代碼細(xì)節(jié)的關(guān)鍵，如初始化，邊界條件，循環(huán)起止條件等。

雖然說(shuō)的好像比較玄乎，但總而言之還是需要經(jīng)驗(yàn)和感覺(jué)，養(yǎng)成一種這樣思維的習(xí)慣。

對(duì)于比較經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題的整理以后再更吧，這里先討論一道比較難以下手的區(qū)間選點(diǎn)問(wèn)題。
Zuma CodeForces - 607B

Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n gemstones, the i-th of which has color ci. The goal of the game is to destroy all the gemstones in the line as quickly as possible.
In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?
Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.
Input
The first line of input contains a single integer n (1?≤?n?≤?500) — the number of gemstones.
The second line contains n space-separated integers, the i-th of which is ci (1?≤?ci?≤?n) — the color of the i-th gemstone in a line.
Output
Print a single integer — the minimum number of seconds needed to destroy the entire line.

題目一看就是區(qū)間選點(diǎn)問(wèn)題，可是我們?nèi)绾芜x那個(gè)點(diǎn)呢？
仔細(xì)分析我們不難發(fā)現(xiàn)，就算我們用一個(gè)分點(diǎn)表示兩個(gè)子列，可是我們并不能判斷中間去掉一部分后形成的回文列應(yīng)該如何處理。似乎難以下手。

接下來(lái)就是比較玄學(xué)的分析階段了。我們仔細(xì)觀察回文列，發(fā)現(xiàn)他們有一個(gè)共同的特征就是兩端的數(shù)字相等，而一個(gè)回文列中間加一個(gè)數(shù)字還是回文列，兩邊加兩個(gè)相同的數(shù)還是回文列。我們不難 得出

if(a[i]==a[j]) dp[i][j]=min(dp[i+1][j-1],dp[i][j]);

然后我們還要注意當(dāng)兩個(gè)相同的在一起的時(shí)候上面的式子可能不成立（i+1>j-1）,所以我們不妨對(duì)兩個(gè)在一起的情況全部分開(kāi)討論一次
然后其他部分還是根據(jù)區(qū)間選點(diǎn)問(wèn)題進(jìn)行處理
下面附AC代碼

#include<cstdio> #include<cstring> using namespace std;int n; int a[505]; int dp[505][505];int min(int a,int b) {return a<b?a:b; } int main() {scanf("%d",&n);memset(a,0,sizeof(a));memset(dp,0x3f,sizeof(dp)); //默認(rèn)是一個(gè)很大的數(shù)for(int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i][i]=1; //對(duì)1個(gè)的時(shí)候進(jìn)行處理}for(int i=1;i<=n-1;i++){if(a[i]==a[i+1]) dp[i][i+1]=1; //將兩個(gè)相鄰的回文數(shù)進(jìn)行處理（因?yàn)闊o(wú)法用上面的那個(gè)式子）else dp[i][i+1]=2;}for(int len=3;len<=n;len++) //區(qū)間長(zhǎng)度從3 開(kāi)始，這種增加區(qū)間長(zhǎng)度而不是循環(huán)端點(diǎn)的寫法還是比較好理解一點(diǎn){for(int i=1;i+len-1<=n;i++){int j=i+len-1;dp[i][j]=min(dp[i][j],dp[i+1][j]+1); //因?yàn)闊o(wú)法處理兩個(gè)相同數(shù)字在一起的情況，所以先拉出來(lái)算if(a[i]==a[i+1])dp[i][j]=min(dp[i][j],dp[i+2][j]+1);//較小一點(diǎn)的區(qū)間已經(jīng)計(jì)算過(guò)了，可以直接使用if(a[i]==a[j]) //對(duì)于兩個(gè)端點(diǎn)相等的情況也不能用區(qū)間選點(diǎn)dp的公式dp[i][j]=min(dp[i][j],dp[i+1][j-1]);for(int k=i+2;k<j;k++)if(a[i]==a[k])dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k+1][j]); }}printf("%d\n",dp[1][n]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/qgmzbry/p/10662102.html

總結(jié)

以上是生活随笔為你收集整理的动态规划浅谈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。