【算法笔记】动态规划Dynamic Programming

参考视频：5 Simple Steps for Solving Dynamic Programming Problems

引子：最长递增子串（Longest Increasing Subsequence，LIS）

LIS([3 1 8 2 5]) = len([1 2 5]) = 3

LIS([5 2 8 6 3 6 9 5]) = len([2 3 6 9]) = 4

解决问题的三个步骤：

1. 可视化例子（visualize example）

（“visualize example”应该是用数据结构表示问题的意思）

使用有向无环图作为工具（directed acyclic graph）

比如[3 1 8 2 5]的LIS的有向无环图就是1->2->5

求LIS的长度就是求有向无环图的最长路径+1

即：LIS = Longest Path in DAG + 1

假如A=[5 2 8 6 3 6 9 5]，要求LIS[5]，怎么办？

LIS[5] = 1 + max

2. 找到问题的子问题（find a appropriate sub-problem）

所有递增子串是原序列的子集；所有递增子串都有头和尾，并且无论头还是尾节点都在原序列中；

因此可以改变头或者尾来得到一个子问题，这里选择尾节点，即：
LIS[k] = LIS ending at index k

例如对于[3 1 8 2 5]，LIS[3] = 2，因为以index=3（即2）的节点为结尾，能找到的LIS就是[1 2]，故长度为3。

3. 找到各个子问题之间的关系

首先思考，在[3 1 8 2 5]中，LIS[4]和之前的子串的关系是什么？

答案是：以index=4为结尾的LIS的前一个节点，有可能是index=0,1,3三种情况（3->5，1->5，1->2->5）

故而要求最长的长度，就是在所有可能的情况中，选出一种最长的再加1，即LIS[4] = max{LIS[0], LIS[1], LIS[3]} + 1

若A=[5 2 8 6 3 6 9 5]，求LIS[5]：

LIS[5] = 1 + max