为你写诗

c/c++
随笔 - 32, 文章 - 0, 评论 - 3, 引用 - 0
数据加载中……

2011年4月23日

最长递增子序列dp

     摘要: 既然已经说到了最长公共子序列,就把这个递增子序列也说了。同样的,这里subsequence表明了这样的子序列不要求是连续的。比如说有子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }这样一个字符串的的最长递增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。

其实这个问题和前面的最长公共子序列问题还是有一定的关联的。假设我们的初始的序列S1。那我们从小到大先排序一下。得到了S1'。这样我们再球S1和S1'的最长公共子序列就可以知道答案了:)是不是有点巧妙啊。这个过程还是比较直观的。但是这个不是这次要说的重点,这个问题有比较传统的做法的.

我们定义L(j)是一个优化的子结构,也就是最长递增子序列.那么L(j)和L(1..j-1)的关系可以描述成

  阅读全文

posted @ 2011-04-23 16:54 pp_zhang 阅读(892) | 评论 (0)编辑 收藏

资料查询

     摘要: http://www.gznc.edu.cn/yxsz/jjglxy/book/Java_api/overview-summary.html  阅读全文

posted @ 2011-04-23 09:44 pp_zhang 阅读(199) | 评论 (0)编辑 收藏