algorithm - 我可以解释一下如何使用最佳子结构来找到这张幻灯片中的最长递增子序列吗？

Question

我目前正在学习如何在我的算法课上寻找最优解，其中一个主题是关于寻找问题中的最优子结构。

到目前为止，我对它的理解是，我们看看是否可以为大小为 n 的问题找到最优解。如果可以，那么我们将问题的规模增加 1，因此它是 n+1。如果n+1的最优解包括n的整个最优解加上+1引入的新解，则我们有最优子结构。

我得到了一个使用最优子结构在给定一组数字的情况下找到最长递增子序列的示例。这显示在此处的 powerpoint 幻灯片上:

谁能给我解释一下幻灯片底部的符号，并证明这个问题可以用最优子结构来解决？

Answer 1

• Lower(i) 表示 S 中当前索引 i 左侧的一组位置 j 使得 S _j 小于 S_i。换句话说，元素 S_j 和 S_i 是递增顺序，即使它们之间可能还有其他元素。
• 左边带大括号的表达式解释了我们如何构建答案:
  1. 第一行表示，如果集合 Lower(i) 为空(即 S_i 是目前序列中最大的数)，则答案为 1。这是基本情况:a单个数字被视为单元素序列
  2. 第二行说如果 Lower(i) 不为空，那么我们从中选择最大的元素，并加 1。换句话说，我们向数字 S_i 的左边看对于另一个小于S_i的数S_j，结束Lower(i)中最长的上升子序列。

所有这些都是编写这六行伪代码的漫长过程:

L[0] = 1
for i = 1..N
    L[i] = 1
    for j = i..0
        if S[i] > S[j] // Member of Lower(i) ?
            L[i] = MAX(L[i], L[j]+1)