我正在学习在我的算法课上寻找最优解，其中一个主题是寻找问题中的最优子结构。
到目前为止，我对它的理解是，我们看看是否能找到一个大小为n的问题的最优解，如果我们能找到，那么我们将问题的大小增加1，所以它是n+1如果n+1的最优解包含了n的全部最优解和+1引入的新解，则我们得到了最优子结构。
我给出了一个例子，在给定一组数的情况下，使用最优子结构来寻找最长的递增子序列。这显示在powerpoint幻灯片中：
有人能给我解释一下幻灯片底部的符号，并证明这个问题可以用最优子结构来解决吗？
最佳答案
下（i）表示当前索引j左侧S中i的一组位置，使得Sj小于Si换言之，sj和si元素的顺序是递增的，尽管它们之间可能还有其他元素。
左大括号的表达式解释了我们如何构造答案：
第一行表示如果集合下限（i）为空（即si是序列中迄今为止最大的数字），那么答案是1。这是基本情况：单个数字被视为一个元素序列
第二行表示如果lower（i）不为空，那么我们从中选择max元素，并添加1。换言之，我们在数字Si的左边寻找另一个小于Si的数字Sj，并结束较低（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)