文件名称：空间优化-dp之子序列
文件大小：529KB
文件格式：PPT
更新时间：2024-05-16 03:16:32
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]} };