接觸動態規劃這么久了，簡單談一下自己對動態規劃的理解。
動態規劃名字聽起來好像比比較高大上，可是事實上，人家就是比較高大上。（抖個機靈）

剛開始接觸動態規劃的時候覺得好可怕，這么復雜的問題我怎么能想的出來，這樣的問題計算機怎么能夠解決？

我覺得動態規劃不是一種準確的算法，而是一種思想，一種特殊的搜索思想。這種思想的本質是將比較復雜的搜索問題變成一個遞推題，而遞推公式就是我們常常提到的狀態轉移方程（可能并不準確，但是我是這樣理解的），或者是說將記憶化搜索的遞歸形式寫成了遞推形式。而問題的核心就是找到傳說中的最優子結構和狀態轉移方程。

對于最優子結構，我們要思考儲存狀態的方式以及特殊的狀態。這種狀態一般比較簡單容易分析。一般是最后一次，因為最后一次的干擾因素比較少，有利于找到問題的核心。而通過對最后狀態的分析結合對狀態的儲存方式寫出狀態轉移方程。

除此之外，對于狀態的分析還需要一定的貪心的思想。

但是寫出狀態轉移方程并不是結束，重要的是通過特殊狀態的狀態轉移方程推廣到一般情況下。這種推廣方式就是我們的代碼結構。
可是這種推廣也不容易一眼看出來（除非你已經有很多經驗或者是你做過比較相似的題），所以我們要從比較簡單的情況結合我們的狀態轉移方程進行分析，這也是完善代碼細節的關鍵，如初始化，邊界條件，循環起止條件等。

雖然說的好像比較玄乎，但總而言之還是需要經驗和感覺，養成一種這樣思維的習慣。

對于比較經典的動態規劃問題的整理以后再更吧，這里先討論一道比較難以下手的區間選點問題。
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.

題目一看就是區間選點問題，可是我們如何選那個點呢？
仔細分析我們不難發現，就算我們用一個分點表示兩個子列，可是我們并不能判斷中間去掉一部分后形成的回文列應該如何處理。似乎難以下手。

接下來就是比較玄學的分析階段了。我們仔細觀察回文列，發現他們有一個共同的特征就是兩端的數字相等，而一個回文列中間加一個數字還是回文列，兩邊加兩個相同的數還是回文列。我們不難 得出

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

然后我們還要注意當兩個相同的在一起的時候上面的式子可能不成立（i+1>j-1）,所以我們不妨對兩個在一起的情況全部分開討論一次
然后其他部分還是根據區間選點問題進行處理
下面附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));	//默認是一個很大的數for(int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i][i]=1;	//對1個的時候進行處理}for(int i=1;i<=n-1;i++){if(a[i]==a[i+1]) dp[i][i+1]=1;	//將兩個相鄰的回文數進行處理（因為無法用上面的那個式子）else dp[i][i+1]=2;}for(int len=3;len<=n;len++)	//區間長度從3 開始，這種增加區間長度而不是循環端點的寫法還是比較好理解一點{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);	//因為無法處理兩個相同數字在一起的情況，所以先拉出來算if(a[i]==a[i+1])dp[i][j]=min(dp[i][j],dp[i+2][j]+1);//較小一點的區間已經計算過了，可以直接使用if(a[i]==a[j])	//對于兩個端點相等的情況也不能用區間選點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;
}