广州城市建设档案馆网站,中国公司排名100强,制作网站软件教程,上海市崇明县建设中学网站接触动态规划这么久了#xff0c;简单谈一下自己对动态规划的理解。 动态规划名字听起来好像比比较高大上#xff0c;可是事实上#xff0c;人家就是比较高大上。#xff08;抖个机灵#xff09;
刚开始接触动态规划的时候觉得好可怕#xff0c;这么复杂的问题我怎么能想…接触动态规划这么久了简单谈一下自己对动态规划的理解。 动态规划名字听起来好像比比较高大上可是事实上人家就是比较高大上。抖个机灵
刚开始接触动态规划的时候觉得好可怕这么复杂的问题我怎么能想的出来这样的问题计算机怎么能够解决
我觉得动态规划不是一种准确的算法而是一种思想一种特殊的搜索思想。这种思想的本质是将比较复杂的搜索问题变成一个递推题而递推公式就是我们常常提到的状态转移方程可能并不准确但是我是这样理解的或者是说将记忆化搜索的递归形式写成了递推形式。而问题的核心就是找到传说中的最优子结构和状态转移方程。
对于最优子结构我们要思考储存状态的方式以及特殊的状态。这种状态一般比较简单容易分析。一般是最后一次因为最后一次的干扰因素比较少有利于找到问题的核心。而通过对最后状态的分析结合对状态的储存方式写出状态转移方程。
除此之外对于状态的分析还需要一定的贪心的思想。
但是写出状态转移方程并不是结束重要的是通过特殊状态的状态转移方程推广到一般情况下。这种推广方式就是我们的代码结构。 可是这种推广也不容易一眼看出来除非你已经有很多经验或者是你做过比较相似的题所以我们要从比较简单的情况结合我们的状态转移方程进行分析这也是完善代码细节的关键如初始化边界条件循环起止条件等。
虽然说的好像比较玄乎但总而言之还是需要经验和感觉养成一种这样思维的习惯。
对于比较经典的动态规划问题的整理以后再更吧这里先讨论一道比较难以下手的区间选点问题。 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[i1][j-1],dp[i][j]); 然后我们还要注意当两个相同的在一起的时候上面的式子可能不成立i1j-1,所以我们不妨对两个在一起的情况全部分开讨论一次 然后其他部分还是根据区间选点问题进行处理 下面附AC代码
#includecstdio
#includecstring
using namespace std;int n;
int a[505];
int dp[505][505];int min(int a,int b)
{return ab?a:b;
}
int main()
{scanf(%d,n);memset(a,0,sizeof(a));memset(dp,0x3f,sizeof(dp)); //默认是一个很大的数for(int i1;in;i){scanf(%d,a[i]);dp[i][i]1; //对1个的时候进行处理}for(int i1;in-1;i){if(a[i]a[i1]) dp[i][i1]1; //将两个相邻的回文数进行处理因为无法用上面的那个式子else dp[i][i1]2;}for(int len3;lenn;len) //区间长度从3 开始这种增加区间长度而不是循环端点的写法还是比较好理解一点{for(int i1;ilen-1n;i){int jilen-1;dp[i][j]min(dp[i][j],dp[i1][j]1); //因为无法处理两个相同数字在一起的情况所以先拉出来算if(a[i]a[i1])dp[i][j]min(dp[i][j],dp[i2][j]1);//较小一点的区间已经计算过了可以直接使用if(a[i]a[j]) //对于两个端点相等的情况也不能用区间选点dp的公式dp[i][j]min(dp[i][j],dp[i1][j-1]);for(int ki2;kj;k)if(a[i]a[k])dp[i][j]min(dp[i][j],dp[i1][k-1]dp[k1][j]); }}printf(%d\n,dp[1][n]);return 0;
}
