专注于互联网--专注于架构

2008年11月27日动态规划:动态规划讲解（二）

上次为了让大家理解动态规划的状态转移方程，特意在做了一大堆分析之后才给出方程。其实对于动态规划的程序，在我们把整个大问题划分成一个个阶段，并确定各个阶段之间的联系之后，就可以直接写出方程式，然后便可以根据方程写出程序。在从此以后的讲解中，我们都会采用这种方式，以加强构造方程的能力。 例题 最长不下降子序列 设有一个正整数的序列：a[1], a[2], …a[n], 对于下标i[1]<i[2]<…i[h], 若有a[i1]<a[i2]<…<a[ih]，则称存在一个长度为h的不下降序列。 例如，下列数 12 51 32 48 132 65 12 47 95 11... [阅读全文] [PDF]