DP的几个著名问题：最长上升子序列（LIS）

本课程是从少年编程网转载的课程，目标是向中学生详细介绍计算机比赛涉及的编程语言，数据结构和算法。编程学习最好使用计算机，请登陆 www.3dian14.org (免费注册，免费学习)。

人的一生也许不需要读太多的书，不过一定要精读几本好书。 无论是数学还是计算机算法，一些问题之所以成为经典，是因为这些问题的思考和解答，构建了思维网络中的关键节点。

知识变成自己的思想， 需要时间的沉淀。一天一题是奔着小镇做题家去的，一周甚至一个月一个新思想，也许才是教育的未来。

今天先介绍最长上升子序列的动态规划思路。

有一个长为n的数列a0, a1, ......, a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列，该问题被称为最长上升子序列（LIS，Longest Increasing Subsequence）的著名问题。

缘起

未成正果的初试

圆满