接触动态规划这么久了，简单谈一下自己对动态规划的理解。
动态规划名字听起来好像比比较高大上，可是事实上，人家就是比较高大上。（抖个机灵）
刚开始接触动态规划的时候觉得好可怕，这么复杂的问题我怎么能想的出来，这样的问题计算机怎么能够解决？
我觉得动态规划不是一种准确的算法，而是一种思想，一种特殊的搜索思想。这种思想的本质是将比较复杂的搜索问题变成一个递推题，而递推公式就是我们常常提到的状态转移方程（可能并不准确，但是我是这样理解的），或者是说将记忆化搜索的递归形式写成了递推形式。而问题的核心就是找到传说中的最优子结构和状态转移方程。
对于最优子结构，我们要思考储存状态的方式以及特殊的状态。这种状态一般比较简单容易分析。一般是最后一次，因为最后一次的干扰因素比较少，有利于找到问题的核心。而通过对最后状态的分析结合对状态的储存方式写出状态转移方程。
除此之外，对于状态的分析还需要一定的贪心的思想。
但是写出状态转移方程并不是结束，重要的是通过特殊状态的状态转移方程推广到一般情况下。这种推广方式就是我们的代码结构。
可是这种推广也不容易一眼看出来（除非你已经有很多经验或者是你做过比较相似的题），所以我们要从比较简单的情况结合我们的状态转移方程进行分析，这也是完善代码细节的关键，如初始化，边界条件，循环起止条件等。
虽然说的好像比较玄乎，但总而言之还是需要经验和感觉，养成一种这样思维的习惯。
对于比较经典的动态规划问题的整理以后再更吧，这里先讨论一道比较难以下手的区间选点问题。
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
",dp[1][n]);
return 0;
}