"longest increasing subsequence" 问题的动态解的成本函数

Question

所以我有一个非常简单的动态规划解决方案来解决“最长递增子序列”问题（找到给定序列中递增元素的最长子序列，例如 [1, 7, 2, 6, 4] 它将是 [1, 2, 4])，它也可以找到实际的子序列（而不是仅仅长度）：

sequence = [1, 8, 6, 4, 9, 8, 3, 5, 2, 7, 1, 9, 5, 7]
listofincreasing = [[] for _ in range(len(sequence))]
listofincreasing[0].append(sequence[0])

for right in range(1, len(sequence)):
    for left in range(right):
        if (sequence[left] < sequence[right]) and (len(listofincreasing[right]) < len(listofincreasing[left])):
            listofincreasing[right] = [] + listofincreasing[left]
    listofincreasing[right].append(sequence[right])

print(max(listofincreasing, key=len))

这类脑筋急转弯对我来说很容易处理，但我真的不知道这背后的硬理论。我的问题是：我将如何创建一个成本函数来正式描述“我如何填写列表”，可以这么说？有人可以告诉我如何解决这个例子中的这些问题吗？提前致谢。

编辑 - 有些人要求澄清。以最简洁的方式，我需要以与此处创建的完全相同的方式创建一个数学函数：https://medium.com/@pp7954296/change-making-problem-dynamic-method-4954a446a511 在“使用动态方法解决硬币变化的公式：”部分，但不是改变问题，但我对最长递增子序列问题的解决方案

Answer 1

您正在寻找动态规划解决方案中重叠子问题的递归公式。

设LONGEST(S,x)为序列S的前x个字符的最长递增子序列。那么问题的解就是LONGEST(S,|S|).

递归（使用基于 1 的索引）：

LONGEST(S,x) = S[1] if x = 1. Otherwise,
LONGEST(S,x) = the longest of:
    S[x],
    LONGEST(S,y), where 1 <= y < x, or
    LONGEST(S,y) + S[x], where 1 <= y < x and LAST_ELMENT(LONGEST(S,y)) < S[x]

由于 LONGEST(S,x) 仅取决于较小前缀的值，我们可以按 x 递增的顺序迭代生成值，这就是您的程序所做的。

"longest increasing subsequence" 问题的动态解的成本函数

Cost function of a dynamic solution to the "longest increasing subsequence" problem

python

algorithm

dynamic-programming

computer-science

theory