“最长增长子序列”问题动态解的代价函数

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的顺序迭代生成值，这就是程序所做的