动态规划的一种常见技巧

动态规划是运筹学的一个分支，是求解决策过程最优化的过程。
动态规划并不是一种算法，而是一种思想，或者说策略
动态规划的思想就是将大问题分解成一个一个的小问题，聚焦到每个小问题并逐个击破，小问题解决了就没有大问题了
我们以一个关于最长递增子序列问题为例，设想你有一个包含N个元素的序列，你的任务是找到最长递增子序列的长度
比如说
列表[3, 1,8,2,5]，最长子序列长度为3，子序列为[1, 2, 5]
列表[5, 2, ,8, 6, 3, 6, 9, 5]最长子序列长度为4， 子序列为[2， 3， 6，9]

需要说明的一个重点是，为了简化，我们目前将专注于寻找序列的长度，而不是序列本身

所以

解决动态规划问题的第一步是寻找一种可视化示例的方式，可视化是发现问题中与解决方案相关的连接和基础模式的有效方法，在解决这个具体问题时，我们显然会遇到一些关于有效序列的约束，因此，找到一种展示有效序列的方式是非常有益的。
在动态规划中，一个常见的模型是有向无环图，设想序列中的每个元素都是图中的一个节点，如果右侧的节点具有更大的值，我们就在两个节点之间建立一个有向边，下面是这个特定输入序列的有向无环图表示，这种表示法的一个优势是，在图中递增子序列仅仅是另一条路径。

实际上，更深入的看，最长递增子序列的长度对应于此有向无环图中最长路径的长度+1，因此，我们在技术上是在计算节点。
对这个特定问题的解决方案可能会变得更加明确，而有时，这种视角的转换正是使挑战问题变得可解的关键。

解决动态规划问题的第二步是找到合适的子问题，子问题实质上是整个问题的简化版，确定子问题可能有一些难度，但让我们关注我们已知的关于这个问题的信息。

我们知道，最长递增子序列会是初始序列的一个特定子集，确定这个子集的一种方法是通过它的起始和终点。
每个递增子序列无论长度如何，都有一个起始点和终点在原始序列中。因此，我们可以通过修改这些变量中的一个，来定义一个子问题

事实上，解决这个问题可以通过任意方法，但我个人觉得关注子序列的终点更为直观

我们为序列定一个子问题，命名为索引k处的lis，这意味着最长递增子序列结束于索引k。例如，结束在3的lis会是从1开始，再到2的序列，长度为2，也就是
lis[3] = 2
记住，当我们讲述这个特定问题中的lis时，我们专门指的是序列的长度。既然我们已经定义了一个可能的子问题，第三步就是要探寻子问题之间的联系。在此阶段，向自己提出一些问题通常会非常有助于思考。例如，假设你想解决找到以索引4结尾的最长上升子序列的问题。为了解这个问题，需要解决哪些子问题呢？

OK，这样图像化的可视化很有用，因为它清晰地展示了我们需要什么样的子问题。经过索引4的一条路径必须从索引0经过，所以我们需要知道以索引0结尾的最长上升子序列的长度，这刚好是1.
另一条路径从索引1经过，我们也需要知道这个子问题的答案，其长度也是1。最终可能以索引4结尾的路径从索引3经过，而以索引3结尾的最长上升子序列的长度是2
lis[0] = 1 lis[1] = 1 lis[3] = 2

因此，最长上升子序列的长度将是1加上所有相关子问题的最大值，即3，直观上来说，这是有道理的对吗？
如果我要找出以索引4结尾的最长上升子序列，我只需要在所有最终能达到索引4的子序列的最长上升子序列之上加1，这确实很有道理
lis[4] = 1 + max{lis[0], lis[1], lis[3] } = 3

所以，一旦我们发现了子问题之间的联系，我们就需要概述这些联系，也就是第四步。
我们再来举一个例子，看看是否能找到一个类似的流程，来解决以索引5结尾的最长上升子序列

这里的核心思想是，我们只考虑以索引k结尾的子问题，当且仅当k小于5，且索引k处的值小于索引5处的值。
为了见证这一关系如何运作，我们从k等于0开始，由于索引0处的位置小于6，我们需要知道这一子问题的解答
我们将继续探讨所有可能的k值，k小于5，并涉及符合题目所述限制的子问题，实际上，所以5并无特殊性
lis[5] = 1 + max{lis[k] | k < 5, A[k] < A[5]}

此逻辑适用于任何n，因此，找到以索引n结尾的最长上升子序列的子问题的一般解即为 1加上所有符合k小于n且索引k处的值小于索引n处的值的k的最大值
lis[n] = 1 + max{lis[k] | k < n, A[k] < A[n]}

现在我们准备开始实现，这是最后一步，也就是第五步，实现一个动态规划方案，其实就是按照适当的顺序解决子问题，最关键的是，在解决某个特定子问题之前，所有相关的子问题都应已解决。对于这个问题，解决问题的顺序实际上相当直观。我们必须从左至右解决子问题。现在，让我们实现一个函数

def lis(A):
    L = [1] * len(A)
    for i in range(1, len(A)):
        subproblems = [L[k] for k in range(i) if A[k] < A[i]]
        L[i] = 1 + max(subproblems, default=0)
    return max(L, default=0)

我们将用一个列表来记录长度，我们可以把所有长度初始化为1，因为每个上升子序列最少包含一个元素
然后，我们会针对输入列表的从1开始的每个索引的长度，首先确定必要的子问题，接着依据我们设定的概述来更新长度
最终，我们会返回刚刚更新的长度列表中的最大长度。实现这个功能有多种方法，因此，不要过于纠结于细节

这里，我们需要记住的一点是，我们应使用一种思维过程，以正确的顺序识别并解决子问题。我们还需要解决最后一个关键问题。直至目前，我们所做的一切，都是为了寻找最长上升子序列的长度。但我们如何真正找到实际的基础序列呢？实际上，这里的关键思路非常简单。我们需要做的，仅仅是为特定的子问题追踪前一个索引。更确切的说，如果我用索引j处的最长上升子序列的值来解决以索引i结尾的最长上升子序列的子问题，那么我可以确定索引i的前一个索引是索引j

我们可以观察一个具体的例子，以便更加清晰的理解。在这个序列中，索引0的前一个索引可以标为-1，因为没有序列值在索引0之前。索引1的前一个索引也一样。
prev[0] = -1 prev[1] = -1
对于索引2，前一个索引可以是索引0或索引1，选择哪一个都没关系，因为他们具有相同的长度值。
prev[2] = 0
而对于索引3，前一个索引只有一个选择，即索引1
prev[3] = 1
最终，索引4只有一种选择，因为计算索引4处的长度的子问题是以索引3为终点的最长上升子序列，因此前一个索引也就是3
prev[4] = 3

这种追踪前一个子问题的模式是解决动态规划问题的一种常见技巧