动态规划
个人理解的动态规划就是, 把大问题分解为好几个小问题, 然后通过保存式搜索的方法, 进行更快的解决. 这更像是递归的优化方法.
示例 最长上升子序列
一个数的序列 bi, 当 b1< b2< ... < bS 的时候, 我们称这
个序列是上升的对于给定的个序列(aaa),
我们可以得到一些上升的子序列(ai1, ai2, ..., aiK), 这里 1
<= i1< i2< ... < iK<= N
? 比如, 对于序列(1, 7, 3, 5, 9, 4, 8), 有它的一些上升子序
列, 如 (1, 7), (3, 4, 8) 等等. 这些子序列中最长的长度是 4,
比如子序列 (1 3 5 8) 或(1 3 4 8)
? 你的任务, 就是对于给定的序列, 求出最长上升子序
列的长度
首先, 如果这道题使用递归的话. 比如, 记 f(n)为一个长度为 n 的子序列, 满足最长上升子序的长度. 但是, 发现, f(n)和 f(n-1), 没有数学关系的联系.
考虑到, 动态规划是, 空间换时间的一种思想.
求 f(n)时, 如果, f(n-1)==n-1, 就是前 n-1 个是一个上升子序, 那么, 只需要判断, a[n]和 a[n-1] 的关系.
但是, 如果, f(n-1)<n-1; 那么, 我们假设我们记录了 f(n-1)对应的包含 a[n-1]的最新上升子序, 同时比较 a[n]和 a[n-1]的大小, 更新最新上升子序, 并比较其长度和 f(n-1), 更新 f(n).
也就是说, 我们需要增加两个 int 型变量, 用于记载包含最新索引元素的上升子序列.
来源: http://www.bubuko.com/infodetail-2737792.html