洛谷P2543LCS,滚动数组优化
LCS dp解法模板题,状态转移方程:
$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
$if(s1[i]==s2[j])$
$dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1)$
普通DP代码:
1 | char s1[10010], s2[10010]; |
数据范围$1e4*1e4$,内存限制$125MB$,可以开出int数组,不过状态转移只与上一维有关,因此可以用滚动数组。
滚动数组DP代码:
1 | char s1[10010], s2[10010]; |