解答不要问我要…………当时听的时候我基本没听懂来着…………老师是这么说的，“动态规划听一遍是肯定听不懂的，不过先听听看吧”
基本上是从老师的课件里拷出来的……
一.去尾型
例:给定数列a1、a2、…、an，求最长递减子序列。
动态规划方程
变量的定义：
ai ::= 数列的第i个数
Si ::= 以ai结尾的最长递减子序列长度
方程：
Si = max{Sk} + 1 0 <= k < i，ak > ai or k = 0
S0 = 0
Answer = max{Si} 1 <= i <= n
类似问题1
一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行，也可以用很快的速度向下飞行，可以毫无损伤地截击进攻导弹，但不可以向后或向上飞行。但有一个缺点，尽管它发射时可以达到任意高度，但它只能截击比它上次截击导弹时所处高度低或者高度相同的导弹。现对这种新型 防卫导弹进行测试，在每一次测试中，发射一系列的测试导弹（这些导弹发射的间隔时间固定，飞行速度相同），该防卫导弹所能获得的信息包括各进攻导弹的高度，以及它们发射次序。现要求编一程序，求在每次测试中，该防卫导弹最多能截击的进攻导弹数量，一个导弹能被截击应满足下列两个条件之一：
1、它是该次测试中第一个被防卫导弹截击的导弹；
2、它是在上一次被截击导弹的发射后发射，且高度不大于上一次被截击导弹的高度的导弹。
类似问题2:
有若干条x轴上的线段，给出它们的左右端点。求这样一个最大的线段集合，使得其中任意两条线段均不重叠。(关于这道题,当时我听到楼天成在跟他同学讲也可以用哈希表,不过我完全迷茫…………）
二.中分型
例:一个a*b的矩阵和一个b*c的矩阵相乘需要a*b*c次乘法，得到一个a*c的矩阵。现在给你一系列矩阵的连乘式，求最少的乘法次数。
动态规划方程
变量的定义：
ri ::= 第i个矩阵的行数
ci ::= 第i个矩阵的列数
Si j ::= 将第i-j个矩阵相乘所需的最少乘法次数
方程：
Si j = max{Si k + Sk+1 j} + ri*ck*cj i <= k <= j
Sii = 0
Answer = S1 n
类似问题:
有n个数a1、a2、…、an。每次从中删去一个数，规定最左最右两个数不能删除。这样共进行n-2次，求得分最高的方案。
计分方式：设某一次删除的数为ai，则你的得分为ai-1*ai*ai+1。所有得分相加即为最后总分。
三.平面型
例:一个迷宫，入口位于左上角，规定只能往下或者往右走。迷宫中存在一些障碍物无法通过。迷宫的某些地方里藏有不同价值的宝藏。求所能收集的宝藏的最大价值。
通常的子结构划分方式：逐行扫描
动态规划方程
变量的定义：
Ai j ::= 迷宫第i行第j列的宝藏价值，-1表示障碍物
Si j ::= 走到第i行第j列所能收集的宝藏的最大价值
方程：
Si j = max{Si j-1，Si-1 j} + Ai j
Si j = -1 Si j-1 = -1 and Si-1 j = -1 or i = 0 or j = 0
S1 1 = A1 1
Answer = Sm n
类似问题:(典型问题，USACO1.4.3)
一个数字三角形如下所示：
3
4 5
9 7 2
6 8 7 4
从顶端出发，每次可以向左下或者右下走。求一条从顶端到底边的路径，使得路径上所有数之和最大。
感觉上背包问题以及以下的题都是这一类型的
给一个带通配符*和?的字符串S，问它能不能匹配字符串T。
例如，a*b?能够匹配aabc，但是不能匹配aab
思路:列表
a a b c
a 1 1 0 0
* 1 1 1 1
b 0 0 1 0
? 0 0 0 1
a a b
a 1 1 0
* 1 1 1
b 0 0 1
? 0 0 0
本格"?":左上为1则本格为1
"*":前一行上为一则本格为1,左为1则本格为1
字母:行列上的字母相同且左上为1,则本格为1
[ 此贴被tctc在2005-11-21 23:36重新编辑 ]
