micxu / algorithm Goto Github PK

Dyanmics Programming
1、适用的范围：
最优化问题

2、基本概念：
一个问题分解为多个阶段来解决，每个阶段有多种决策，每个决策会带来收益，每个阶段的收益只 取决于当前状态和决策；

3、特点：
子问题有大量的重叠，一般应对此种问题需要的方案是打表避免重复，但是这个解决方案是通过空间换时间的方式来解决问题。

4、一般解题步骤：
1> 确定状态和收益
2> 初始状态和终止状态
3> 确定决策集合
4> 是否无后效性
5> 收益如何表示

   主要问题：如何把问题转化成状态转移方程，也就是如何描述收益，从一个阶段到另一个阶段。

实例一：LIS(Longest Increasing Subsequence)
问题：给定一个数列，求它的最长单增的子序列。如，给定10,4,20,10,15,13则{4,10,15}和{4,10,13}都是解
解题步骤：

1. 确定状态和收益：f(i)表示以第i项结尾的最长单增子序列的长度；
2. 初始状态：f(0) = 0
   终止状态：max{f(1), f(2), f(3) ... f(i)};
3. 确定决策集合：已知全部决策f(x), x < i, 如果ai > ax,则显然可以把ai连接在ax的后面；
4. 无后效性： f(i)只与决策x相关；
5. 收益表示：由定义f(i) = max{f(x)| x < i且ai>ax｝ ＋ 1， 如果该集合是空集，则对应max值为0。