【文件属性】：
文件名称：空间优化-dp之子序列
文件大小：529KB
文件格式：PPT
更新时间：2021-04-26 09:29:52
dp之子序列
空间优化
如果只需要最优值, 可以用滚动数组实现
按照i递增的顺序计算, dp[i,j]只和dp[i-1,j]和dp[i,j-1]以及dp[i-1,j-1]有关系，因此只需要保留相邻两行, 空间复杂度为O(min{m,n})
更进一步的, 可以只保留一行, 每次用单独的变量x保留d[i-1,j], 则递推方程为
If(i==j) d[j]=x;
else { x = d[j]; d[j]=max{d[j-1], d[j]} };