Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

short水过，可是…哪位大牛能告诉我，为什么一样的dp,滚动数组能比[5001][5001]省2/3的时间？？？？？？？

Posted by JokerKS at 2010-10-04 13:41:38 on Problem 1159

RT,
……
dp[i][j]表示从i到j的子串的最优解,s[]是字符串
for(……)
    if(s[i]==s[j])dp[i][j]=dp[i+1][j-1];
    else          dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
1400MS+才过
可换成滚动数组：
for(……)
    if(s[i]==s[j]) dp[pre][i]=dp[pre][i+1];
    else  dp[pre][i]=min(dp[nw][i],dp[nw][i+1])+1;
nw=!nw;pre=!pre;
600MS-就过了……
这两者计算的次数应该没啥差别吧？应该都是n+(n-1)+(n-2)+……+1啊
为什么会……

Followed by:

Re:short水过，可是…哪位大牛能告诉我，为什么一样的dp,滚动数组能比[5001][5001]省2/3的时间？？？？？？？ (18) yy17yy 2010-10-31 00:13:10

Post your reply here:

Home Page Go Back To top