hdoj 1513 Palindrome 【LCS】+【滚动数组】
Palindrome
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 3276 Accepted Submission(s): 1134
As an example, by inserting 2 characters, the string "Ab3bd" can be transformed into a palindrome ("dAb3bAd" or "Adb3bdA"). However, inserting fewer than 2 characters does not produce a palindrome.
5 Ab3bd
2#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> using namespace std; char str[5010]; char s[5010]; int dp[2][5010]; //dp[5010][5010], int main() { int n; while(~scanf("%d",&n)) { int i,j; scanf("%s",str); for(i=0;i<n;i++) { //scanf("%c",&str[i]);//Output Limit Exceeded s[n-1-i]=str[i]; } memset(dp, 0, sizeof(dp)); //dp的无后效性,可以优化内存,运用滚动数组 for(i = 1; i <= n; i ++) { for(j = 1; j <= n; j++) { if(str[i-1] == s[j-1]) dp[i%2][j] = dp[(i-1)%2][j-1] + 1;//dp[i][j]=dp[i-1][j-i]+1; else dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1]); // dp[i][j] = max(dp[i-1][j], dp[i][j-1]) } } printf("%d\n", n-dp[n%2][n]); //n-dp[n][n] } return 0; }<span style="font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;">滚动数组实际是一种节省空间的办法,时间上没啥优势,多用于DP中,举个例子吧: </span><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"></p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"></p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;">一个DP,平常如果需要1000×1000的空间,其实根据DP的<strong>无后效性</strong>,可以开成2×1000,然后通过滚动,获得和1000×1000一样的效果。滚动数组常用于DP之中,在DP过程中,我们在由一个状态转向另一个状态时,很可能之前存储的某些状态信息就已经无用了,例如在01背包问题中,从理解角度讲我们应开DP[i][j]的二维数组,第一维我们存处理到第几个物品,也就是阶段了,第二维存储容量,但是我们获得DP[i],只需使用DP[i - 1]的信息,DP[i - k],k>1都成了无用空间,因此我们可以将数组开成一维就行,迭代更新数组中内容,滚动数组也是这个原理,目的也一样,不过这时候的问题常常是不可能缩成一维的了,比如一个DP[i][j]需要由DP[i - 1 ][k],DP[i - 2][k]决定,i<n,0<k<=10;n <= 100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组,结果很明显,超内存,其实我们只要开DP[3][11]就够了DP[i%3][j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定,空间复杂度差别巨大。</p><p style="margin-top: 0px; margin-bottom: 0px; padding-top: 0px; padding-bottom: 0px; font-family: Arial; font-size: 14.44444465637207px; line-height: 25.98958396911621px;"><span style="background-color: rgb(245, 245, 245); color: rgb(51, 51, 51); font-family: Helvetica, Tahoma, Arial, sans-serif; line-height: 24px;"><strong>无后效性</strong>,就是说当前状态是历史的完全总结,和如何达到这一个状态无关。</span></p>
例如,对于这道单词接龙的题目,每个单词最多用两次。
那么“当前接到的单词”就不能概括整个“历史”,因为同样是接到的这个单词,以前考虑过的单词究竟是用过
没有,用过多少次,将同样影响今后的发展,而单一的状态参量无法概括这些信息。如果把这些信息加到状态
参量中,状态太多(指数级),动态规划也没有多大意义。
如果影响历史的信息并不多,我们可以通过升维的方法让我们的状态具有无后效性,
所以我们在思考状态的时候,指导思想就是“简洁而又完全的概括历史”
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。