动态规划:LCS最长公共子序列

    技术2024-08-10  64

    一、最长公共子序列 不要求连续,可以跳着挑 子序列: 暴力算法是指数时间

    然后分成三种情况:分别判断最后一个元素: 不相等的时候,就不用考虑最后一个元素了

    表示成数学: 2 , 3情况取值最大的。 这就是备忘录表。

    这里面的zk是当前情况下的最后一个

    二:递归算法实现

    使用备忘录:就是找一个数组存住重复子问题的解

    算法描述: 寻找最优的解: 从表格的最后一个元素开始向上寻找: 这张表格式算法生成的,现在是寻找子序列

    Processed: 0.255, SQL: 9