最长公共子序列的特殊情况,该怎么处理
最长公共子序列的特殊情况
最长公共子序列的特殊情况，没让求最长是多少，只让求是否大于n-5...
输入两个序列 X, Y. 长度都为 n
输出：Yes, 如果最长公共子序列的长度至少是n-5.
NO, 如果不是。
找到一个O(n) time, O(n) space的算法。
证明算法的正确性
------解决方案--------------------
dp和朴素的一模一样。注意到dp[i][j]当
------解决方案--------------------
i-j
------解决方案--------------------
>5的时候就没有意义，所以可以强制令他们为0。然后针对
------解决方案--------------------
i-j
------解决方案--------------------
<=5的时候做正常dp就行。这个算法能保证如果LCS至少n-5的话，dp[i][j]能求得正确的LCS（因为dp最优路径上的计算都和原来一样）。
但是计算过程中只存储
------解决方案--------------------
i-j
------解决方案--------------------
<=5的元素，计算的时候也只对它们进行计算。n-5换成n-k的话这玩意的空间O(k*n)，时间O(k^2*n)，但是这里k=5常数，所以k项全压到O(1)，就线性了。
------解决方案--------------------
http://my.****.net/my/album/detail/1748861#464276
最长公共子序列的特殊情况，没让求最长是多少，只让求是否大于n-5...
输入两个序列 X, Y. 长度都为 n
输出：Yes, 如果最长公共子序列的长度至少是n-5.
NO, 如果不是。
找到一个O(n) time, O(n) space的算法。
证明算法的正确性
------解决方案--------------------
dp和朴素的一模一样。注意到dp[i][j]当
------解决方案--------------------
i-j
------解决方案--------------------
>5的时候就没有意义，所以可以强制令他们为0。然后针对
------解决方案--------------------
i-j
------解决方案--------------------
<=5的时候做正常dp就行。这个算法能保证如果LCS至少n-5的话，dp[i][j]能求得正确的LCS（因为dp最优路径上的计算都和原来一样）。
但是计算过程中只存储
------解决方案--------------------
i-j
------解决方案--------------------
<=5的元素，计算的时候也只对它们进行计算。n-5换成n-k的话这玩意的空间O(k*n)，时间O(k^2*n)，但是这里k=5常数，所以k项全压到O(1)，就线性了。
------解决方案--------------------
http://my.****.net/my/album/detail/1748861#464276