一、最长公共子序列 不要求连续,可以跳着挑 子序列: 暴力算法是指数时间
然后分成三种情况:分别判断最后一个元素: 不相等的时候,就不用考虑最后一个元素了
表示成数学: 2 , 3情况取值最大的。 这就是备忘录表。
这里面的zk是当前情况下的最后一个
二:递归算法实现
使用备忘录:就是找一个数组存住重复子问题的解
算法描述: 寻找最优的解: 从表格的最后一个元素开始向上寻找: 这张表格式算法生成的,现在是寻找子序列