基于连通性状态压缩的动态规划问题
长沙市雅礼中学陈丹琦
【摘要】
基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题．在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究．本文主要从动态规划的几个步骤——划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨．结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得．
【关键词】
状态压缩连通性括号表示法轮廓线插头棋盘模型
【目录】
【序言】 (3)
【正文】 (5)
一. 问题的一般解法 (5)
【例1】Formula 1 (5)
问题描述 (5)
算法分析 (5)
小结 (11)
二. 一类简单路径问题 (12)
【例2】Formula 2 (15)
问题描述 (15)
算法分析 (15)
小结 (16)
三. 一类棋盘染色问题 (17)
【例3】Black & White (17)
问题描述 (17)
算法分析 (17)
小结 (19)
四. 一类基于非棋盘模型的问题 (20)
【例4】生成树计数 (20)
问题描述 (20)
算法分析 (20)
小结 (21)
五. 一类最优性问题的剪枝技巧 (22)
【例5】Rocket Mania (22)
问题描述 (22)
算法分析 (23)
小结 (25)
六.总结 (25)
【参考文献】 (26)
【感谢】 (26)
【附录】 (26)
【序言】
先看一个非常经典的问题——旅行商问题(即TSP 问题，Traveling Salesman Problem)：一个n(≤15)个点的带权完全图，求权和最小的经过每个点恰好一次的封闭回路．这个问题已经被证明是NP 完全问题，那么对于这样一类无多项式算法的问题，搜索算法是不是解决问题的唯一途径呢? 答案是否定的．不难发现任何时候我们只需要知道哪些点已经被遍历过而遍历点的具体顺序对以后的决策是没有影响的，因此不妨以当前所在的位置i ，遍历过的点的集合S 为状态作动态规划：
(,)m i n {(,{})(f i S f j S i d i s t j i =-+，其中j<>i ，i ，j in S ．
动态规划的时间复杂度为2(2*)n O n ，虽然为指数级算法，但是对于n = 15的数据规模来说已经比朴素的(!)O n 的搜索算法高效很多了．我们通常把这样一类以一个集合内的元素信息作为状态且状态总数为指数级别的动态规划称为基于状态压缩的动态规划或集合动态规划．基于状态压缩的动态规划问题通常具有以下两个特点：1．数据规模的某一维或几维非常小；2．它需要具备动态规划问题的两个基本性质：最优性原理和无后效性．
一般的状态压缩问题，压缩的是一个小范围内每个元素的决策，状态中元素的信息相对独立．而有些问题，仅仅记录每个元素的决策是不够的，不妨再看一个例子：给你一个m * n (m, n ≤9) 的矩阵，每个格子有一个价值,i j V ，要求找一个连通块使得该连通块内所有格子的价值之和最大．按从上到下的顺序依次考虑每个格子选还是不选，下图为一个极端情况，其中黑色的格子为所选的连通块．只考虑前5行的时候，所有的黑色格子形成了三个连通块，而最后所
有的黑色格子形成一个连通块．如果状态中只单纯地
记录前一行或前几行的格子选还是不选，是无法准确
描述这个状态的，因此压缩的状态中我们需要增加一
维，记录若干个格子之间的连通情况．我们把这一类
必须要在状态中记录若干个元素之间的连通信息的问
题称为基于连通性状态压缩的动态规划问题．本文着
重对这类问题进行研究．
连通是图论中一个非常重要的概念，在一个无向图中，如果两个顶点之间存在一条路径，则称这两个点连通．而基于连通性状态压缩的动态规划问题与图论模型有着密切的关联，比如后文涉及到的哈密尔顿回路、生成树等等．通常这类问题的本身与连通性有关或者隐藏着连通信息．
全文共有六个章节．
第一章，问题的一般解法，介绍解决基于连通性状态压缩的动态规划问题的一般思路和解题技巧；
第二章，一类简单路径问题，介绍一类基于棋盘模型的简单路径问题的状态表示的改进——括号表示法以及提出广义的括号表示法；
第三章，一类棋盘染色问题，介绍解决一类棋盘染色问题的一般思路；
第四章，一类基于非棋盘模型的问题，介绍解决一类非棋盘模型的连通性状态压缩问题的一般思路；
第五章，一类最优性问题的剪枝技巧，本章的重点是优化，探讨如何通过剪枝来减少扩展的状态的总数从而提高算法的效率；
第六章，总结，回顾前文，总结解题方法．
【正文】
一. 问题的一般解法
基于连通性状态压缩的动态规划问题通常具有一个比较固定的模式，几乎所有的题目都是在这个模式的基础上变形和扩展的．本章选取了一个有代表性的例题来介绍这一类问题的一般解法．
【例1】Formula 11
问题描述
给你一个m * n的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次．m, n ≤ 12．
如图，m = n = 4，(1, 1), (1, 2)是障碍，共有2条满足要求的回路．
算法分析
【划分阶段】这是一个典型的基于棋盘模型的问题，棋盘模型的特殊结构，使得它成为连通性状态压缩动态规划问题最常见的“舞台”．通常来说，棋盘模型有三种划分阶段的方法：逐行，逐列，逐格．顾名思义，逐行即从上到下或从下到上依次考虑每一行的状态，并转移到下一行；逐列即从左到右或从右到左依次考虑每一列的状态，并转移到下一列；逐格即按一定的顺序(如从上到下，从左到右)依次考虑每一格的状态，并转移到下一
个格子．
对于本题来说，逐行递推和逐列递推基本类似2，接
下来我们会对逐行递推和逐格递推的状态确立，状态转
移以及程序实现一一介绍．
1Ural1519, Timus Top Coders : Third Challenge
2有的题目, 逐行递推和逐列递推的状态表示有较大的区别, 比如本文后面会讲到的Rocket Mania一题
【确立状态】 先提出一个非常重要的概念——“插头”．对于一个4连通的问题来说，它通常有上下左右4个插头，一个方向的插头存在表示这个格子在这个方向可以与外面相连．本题要求回路的个数，观察可以发现所有的非障碍格子一定是从一个格子进来，另一个格子出去，即4个插头恰好有2个插头存在，共6种情况．
逐行递推 不妨按照从上到下的顺序依次考虑每
一行．分析第i 行的哪些信息对第i + 1行有影响：
我们需要记录第i 行的每个格子是否有下插头，这决
定了第i+1行的每个格子是否有上插头．仅仅记录插
头是否存在是不够的，可能导致出现多个回路 (如右
图)，而本题要求一个回路，也就隐含着最后所有的非障碍格子通过插头连接成了一个连通块，因此还需要记录第i 行的n 个格子的连通情况．
插头：0011 插头：1111 插头：10013
连通性：(3,4) 连通性：(1,2) (3,4) 连通性：(1,2,3,4)4
我们称图中的蓝线为轮廓线，任何时候只有轮廓线上方与其直接相连的格子和插头才会对轮廓线以下的格子产生直接的影响．通过上面的分析，可以写出动态规划的状态：01(,,)f i S S 表示前i 行，第i 行的n 个格子是否具有下插头的一个n 位的二进制数为0S ，第i 行的n 个格子之间的连通性为1S 的方案总数．
如何表示n 个格子的连通性呢? 通常给每一个格子标记一个正数，属于同一个的连通块的格子标记相同的数．比如{1,1,2,2}和{2,2,1,1}都表示第1,2个格子属于一个连通块，第3,4个格子属于一个连通块．为了避免出现同一个连通信息有不同的表示，一般会使用最小表示法．
一种最小表示法为：所有的障碍格子标记为0，第一个非障碍格子以及与它连通的所有格子标记为1，然后再找第一个未标记的非障碍格子以及与它连通的格子标记为2，……，重复这个过程，直到所有的格子都标记完毕．比如连通信息((1,2,5),(3,6),(4))表示为{1,1,2,3,1,2}．还有一种最小表示法，即一个连通块内所有的格子都标记成该连通块最左边格子的列编号，比如上面这个例子，我们表
3
从左到右, 0表示无插头, 1表示有插头 4 括号内的数表示的是格子的列编号, 一个括号内的格子属于一个连通块
示为{1,1,3,4,1,3}．两种表示方法在转移的时候略有不同，本文后面将会提到5．如上图三个状态我们可以依次表示为2(1,(0011),{0,0,1,1})f ，2(2,(1111),{1,1,2,2})f ，2(3,(1001),{1,1,1,1})f ．
状态表示的优化 通过观察可以发现如果轮廓线上方的n 个格子中某个格子没有下插头，那么它就不会再与轮廓线以下的格子直接相连，它的连通性对轮廓线以下的格子不会再有影响，也就成为了“冗余”信息．不妨将记录格子的连通性改成记录插头的连通性，如果这个插头存在，那么就标记这个插头对应的格子的连通标号，如果这个插头不存在，那么标记为0．这样状态就从01(,,)f i S S 精简为(,)f i S ，上图三个状态表示为(1,{0,0,1,1})f ，(2,{1,1,2,2})f ，(3,{1,0,0,1})f ．
优化后不仅状态表示更加简单，而且状态总数将会大大减少．
逐格递推 按照从上到下，从左到右的顺序依次考虑每一格．分析转移完(i, j)这个格子后哪些信息对后面的决策有影
响：同样我们可以刻画出轮廓线，即轮廓
线上方是已决策格子，下方是未决策格
子．由图可知与轮廓线直接相连的格子有
n 个，直接相连的插头有n+1个，包括n
个格子的下插头以及(i, j)的右插头．为了
保持轮廓线的“连贯性”，不妨从左到右依
次给n 个格子标号，n+1个插头标号．类似地，我们需要记录与轮廓线直接相连的n+1个插头是否存在以及n 个格子的连通情况．
通过上面的分析，很容易写出动态规划的状态：01(,,,)f i j S S 表示当前转移完(i, j)这个格子，n+1个插头是否存在表示成一个n+1位的二进制数S 0，以及n 个格子的连通性为S 1的方案总数．
2(3,1,(10111),{1,1,2,2})f 2(3,2,(10111),{1,1,2,2})f 2(3,3,(10001),{1,1,1,1})f 逐行递推的时候我们提到了状态的优化，同样地，我们也可以把格子的连通性记录在插头上，新的状态为(,,)f i j S ，上图3个状态依次为(3,1,{1,0,1,2,2})f ，(3,2,{1,0,1,2,2})f ，(3,3,{1,0,0,0,1})f ．
5因为第一种表示法更加直观, 本文如果不作特殊说明, 默认使用第一种最小表示法
【转移状态】
状态的转移开销主要包含两个方面：每个状态转移的状态数，计算新的状态的时间．
逐行递推 假设从第i 行转移到第i+1行，我们需要枚举第i+1行的每个格子的状态(共6种情况)，对于任何一个非障碍格子，它是否有上插头和左插头已知，因此最多只有2种情况，状态的转移数≤2n ．
枚举完第i+1行每个格子的状态后，需要计算第i+1行n 个格子之间的连通性的最小表示，通常可以使用并查集的Father 数组对其重新标号或者重新执行一次BFS/DFS ，时间复杂度为O(n)，最后将格子的连通性转移到插头的连通性上．
特别需要注意的是在转移的过程中，为了避免出现多个连通块，除了最后一行，任何时候一个连通分量内至少有一个格子有下插头．
逐格递推 仔细观察下面这个图，当(,1,)f i j S 转移到(,,')f i j S 时，轮廓
线上n 个格子只有(i-1, j)被改成(i, j)，n+1个插头只有2个插头被改动，即(i, j-1)的右插头修改成(i, j)的下插头和(i-1，j)的下插头修改成(i, j)的右插头．转移的时候枚举(i, j)的状态分情况讨论．一般棋盘模型的逐格递推转移有3类情况：新建一个连通分量，合并两个连通分量，以及保持原来的连通分量．下面针对本题进行分析：
情况1 新建一个连通分量，这种情况出现在(i, j)
有右插头和下插头．新建
Condition I
Condition III
Condition II
的两个插头连通且不与其它插头连通，这种情况下需要将这两个插头连通分量标号标记成一个未标记过的正数，重新O(n)扫描保证新的状态满足最小表示．
情况2 合并两个连通分量，这种情况出现在(i, j)有上插头和左插头．如果两个插头不连通，那么将两个插头所处的连通分量合并，标记相同的连通块标号，O(n)扫描保证最小表示；如果已经连通，相当于出现了一个回路，这种情况只能出现在最后一个非障碍格子．
情况3 保持原来的连通分量，这种情况出现在(i, j)的上插头和左插头恰好有一个，下插头和右插头也恰好有一个．下插头或右插头相当于是左插头或上插头的延续，连通块标号相同，并且不会影响到其他的插头的连通块标号，计算新的状态的时间为O(1)．
注意当从一行的最后一个格子转移到下一行的第一个格子的时候，轮廓线需要特殊处理．值得一提的是，上面三种情况计算新的状态的时间分别为O(n), O(n), O(1)，如果使用前面提到的第二种最小表示方法，情况1只需要O(1)，但是情况3可能需要O(n)重新扫描．
比较一下逐行递推和逐格递推的状态的转移，逐行递推的每一个转移的状态总数为指数级，而逐格递推为O(1)，每次计算新的状态的时间两者最坏情况都为O(n)，但是逐行递推的常数要比逐格递推大，从转移开销这个角度来看，逐格递推的优势是毋庸置疑的．
【程序实现】
逐行递推和逐格递推的程序实现基本一致，下面以逐格递推为例来说明．首先必须解决的一个问题是，对于像(3,2,{1,0,1,2,2})f 这样的一个状态我们该如何存储，可以开一个长度为n+1的数组来存取n+1个插头的连通性，但是数组判重并不方便，而且空间较大．不妨将n+1个元素进行编码，用一个或几个整数来存储，当我们需要取一个状态出来对它进行修改的时候再进行解码．
编码最简单的方法就是表示成一个n+1位的p 进制数，p 可以取能够达到的最大的连通块标号加16，对本题来说，最多出现/26n ≤????个连通块，不妨取p =
7．在不会超过数据类型的范围的前提下，建议将p 改成2的幂，因为位运算比普通的运算要快很多，本题最好采用8进制来存储．
如需大范围修改连通块标号，最好将状态O(n) 解码到一个数组中，修改后再O(n)计算出新的p 进制数，而对于只需要局部修改几个标号的情况下，可以直接用(x div p i-1) mod p 来获取第i 位的状态，用1*i k p -±直接对第i 位进行修改．
最后我们探讨一下实现的方法，一般有两种方法：
6 因为还要把0留出来存没有插头的情况
1．对所有可能出现的状态进行编码，枚举编码方式：预处理将所有可能的 连通性状态搜索出来，依次编号1, 2, 3, …,Tot ，那么状态为(,,)f i j k 表示转移完(i, j)后轮廓线状态编号为k 的方案总数．将所有状态存入Hash 表中，使得每个状态与编号一一对应，程序框架如下：
2．记忆化宽度优先搜索：将初始状态放入队列中，每次取队首元素进行扩展，并用Hash 对扩展出来的新的状态判重．程序框架如下：
比较上述两种实现方法，直接编码的方法实现简单，结构清晰，但是有一个很大的缺点：无效状态可能很多，导致了很多次空循环，而大大影响了程序的效率．下面是一组实验的比较数据：
表1．直接编码与宽度优先搜索扩展状态总数比较 测试数据 宽度优先搜索 扩展状态总数
直接编码 Tot Tot * m * n 无效状态比率 m = 9, n = 9
(1,1)为障碍
30930 2188 177228 82.5% m = 10, n =
10
无障碍 134011 5798 579800 76.8%
For i ← 1 to m
For j ←1 to n
For k ← 1 to Tot
For x ← (i , j , State [k ]) 的所有转移后的状态
'k ← 状态x 的编号
(,,)(,,)(,,)f i j k f i j k f i j k ''''''←+，(,)i j ''为(,)i j 的后继格子．
End For
Queue.Push(所有初始状态) While not Empty(Queue) p ← Queue.Pop() For x ← p 的所有转移后的状态 If x 之前扩展过 Then Sum [x ] ← Sum[x ] + Sum[p ] Else Queue.Push(x ) Sum[x ] ← Sum[p ] End If End For End While
可以看出直接编码扩展的无效状态的比率非常高，对于障碍较多的棋盘其对比更加明显，因此通常来说宽度优先搜索扩展比直接编码实现效率要高．
Hash 判重的优化：使用一个HashSize 较小的Hash 表，每转移一个(i, j)清空一次，每次判断状态x 是否扩展过的程序效率比用一个HashSize 较大的Hash 表每次判断状态(i, j, x)高很多．类似地，在不需要记录路径的情况下，也可以使用滚动的扩展队列来代替一个大的扩展队列．
最后我们比较一下，不同的实现方法对程序效率的影响7：
Program 1 ：8-Based ，枚举编码方式．
Program 2 ：8-Based ，队列扩展，HashSize = 3999997．
Program 3 ：8-Based ，队列扩展，HashSize = 4001，Hash 表每次清空． Program 4 ：7-Based ，队列扩展，HashSize = 4001，Hash 表每次清空．
表2．不同的实现方法的程序效率的比较 测试数据
Program 1 Program 2 Program 3 Program 4 m = 10, n = 10
无障碍棋盘
46ms 31ms 15ms 31ms m = 11, n = 11
(1,1)为障碍
140ms 499ms 109ms 187ms m = 12, n = 12
无障碍 624ms 1840ms 499ms 873ms
小结
本章从划分阶段，确立状态，状态转移以及程序实现四个方面介绍了基于连通性状态压缩动态规划问题的一般解法，并在每个方面归纳了一些不同的方法，最后对不同的算法的效率进行比较．在平时的解题过程中我们要学会针对题目的特点和数据规模“对症下药”，选择最合适的方法而达到最好的效果．
由于逐格递推的转移开销比逐行递推小很多，下文如果不作特殊说明，我们都采用逐格的阶段划分．
7 测试环境: Intel Core2 Duo T7100, 1.8GHz, 1G 内存
m = 11, n = 11
(1,1)为障碍
333264 15511 1876831 82.2% m = 12, n =
12
无障碍 1333113 41835 6024240 77.9%
二. 一类简单路径问题
这一章我们会针对一类基于棋盘模型的简单回路和简单路径问题的解法作一个探讨．简单路径，即除了起点和终点可能相同外，其余顶点均不相同的路径，而简单回路为起点和终点相同的简单路径．Formula 1是一个典型的棋盘模型的简单回路问题，这一章我们继续以这个题为例来说明．
首先我们分析一下简单回路问题有什么特点：
仔细观察上面的图，可以发现轮廓线上方是由若干条互不相交的路径构成的，而每条路径的两个端口恰好对应了轮廓线上的两个插头! 一条路径上的所有格子对应的是一个连通块，而每条路径的两个端口对应的两个插头是连通的而且不与其他任何一个插头连通．
在上一章我们提到了逐格递推转移的时候的三种情况：新建一个连通分量，合并两个连通分量，保持原来的连通分量，它们分别等价于两个插头成为了一条新的路径的两端，两条路径的两个端口连接起来形成一条更长的路径或一条路径的两个端口连接起来形成一个回路以及延长原来的路径．
通过上面的分析我们知道了简单回路问题一定满足任何时候轮廓线上每一个连通分量恰好有2个插头，那么这些插头之间有什么性质呢?
【性质】轮廓线上从左到右4个插头a, b, c, d，如果a, c连通，并且与b不连通，那么b, d一定不连通．
证明：反证法，如果a, c连通，b, d连通，那么轮
廓线上方一定至少存在一条a到c的路径和一条b到d
的路径．如图，两条路径一定会有交点，不妨设两条路
径相交于格子P，那么P既与a, c连通，又与b, d连通， d
c
a b
可以推出a, c 与b, d 连通，矛盾，得证．
这个性质对所有的棋盘模型的问题都适用．
“两两匹配”，“不会交叉”这样的性质，我们很容易联想到括号匹配．将轮廓线上每一个连通分量中左边那个插头标记为左括号，右边那个插头标记为右括号，由于插头之间不会交叉，那么左括号一定可以与右括号一一对应．这样我们就可以使用3进制——0表示无插头，1表示左括号插头，2表示右括号插头记录下所有的轮廓线信息．不妨用#表示无插头，那么上面的三幅图分别对应的是(())#()，(()#)()，(()###)，即333(1122012),(1120212),(1120002)，我们称这种状态的表示方法为括号表示法．
依然分三类情况来讨论状态的转移：
为了叙述方便，不妨称(i,j-1)的右插头为p ，(i-1, j)的下插头为q ，(i, j)的下插头为p '，右插头为q '，那么每次转移相当于轮廓线上插头p 的信息修改成p '的信息，插头q 的信息修改成q '的信息，设W(x) = 0, 1, 2表示插头x 的状态．
情况1 新建一个连通分量，这种情况下W(p) = 0，W(q) = 0，p '，q '两个插头构建了一条新的路径，相当于p '为左括号，q '为右括号，即()W p '← 1，()W q '← 2，计算新的状态的时间为O(1)．
情况2 合并两个连通分量，这种情况下W(p) > 0，W(q) > 0，()W p '← 0，()W q '← 0，根据p, q 为左括号还是右括号分四类情况讨论：
情况2.1 W(p) = 1，W(q) = 1．那么需要将q 这个左括号与之对应的右括号v 修改成左括号，即W(v) ← 1．
情况2.2 W(p) = 2，W(q) = 2．那么需要将p 这个右括号与之对应的左括号v 修改成右括号，即W(v)← 2．
情况2.3 W(p) = 1，W(q) = 2，那么p 和q 是相对应的左括号和右括号，连接p, q 相当于将一条路径的两端连接起来形成一个回路，这种情况下只能出现在最后一个非障碍格子．
情况2.4 W(p) = 2，W(q) = 1，那么p 和q 连接起来后，p 对应的左括号和q 对应的右括号恰好匹配，不需要修改其他的插头的状态．
q p v ( ) 情况2.1图 q p ( v ) 情况2.2图
情况2.1, 2.2需要计算某个左括号或右括号与之匹配的括号，这个时候需要对三进制状态解码，利用类似模拟栈的方法．因此情况2.1, 2.2计算新的状态的时间复杂度为O(n)，2.3, 2.4时间复杂度为O(1)．
情况3 保持原来的连通分量，W(p)，W(q)中恰好一个为0，()W p '，()W q '中也恰好一个为0．那么无论p '，q '中哪个插头存在，都相当于是p, q 中那个存在的插头的延续，括号性质一样，因此()W p '← W(p) + W(q)，()W q '← 0或者()W q '← W(p) + W(q)，()W p '← 0．计算新的状态的时间复杂度为O(1)．
通过上面的分析可以看出，括号表示法利用了简单回路问题的“一个连通分量内只有2个插头”的特殊性质巧妙地用3进制状态存储下完整的连通信息，插头的连通性标号相对独立，不再需要通过O(n)扫描大范围修改连通性标号．实现的时候，我们可以用4进制代替3进制而提高程序运算效率，下面对最小表示法与括号表示法的程序效率进行比较：
表3．不同的状态表示的程序效率的比较 测试数据
最小表示法 7Based 最小表示法 8Based 括号表示法 3Based 括号表示法 4Based m = 10, n = 10
无障碍棋盘
31ms 15ms 0ms 0ms m = 11, n = 11
(1,1)为障碍 187ms 109ms 46ms 31ms m = 12, n = 12
无障碍 873ms 499ms 265ms 140ms
可以看出，括号表示法的优势非常明显，加上它的思路清晰自然，实现也更加简单，因此对于解决这样一类简单回路问题是非常有价值的．
类似的问题还有：NWERC 2004 Pipes ，Hnoi2004 Postman ，Hnoi2007 Park ，还有一类非回路问题也可以通过棋盘改造后用简单回路问题的方法解决，比如 POJ 1739 Tony ’s Tour ：给一个m * n 棋盘，有的格子是障碍，要求从左下角走到右下角，每个格子恰好经过一次，问方案总数．(m, n ≤ 8)
只需要将棋盘改造一下，问题就等价于Formula 1了．
.......
#.. 改造成 .#####.
p q 情况2.3图 p q ( ) 情况2.4图
... .##..#.
.......
介绍完简单回路问题的解法，那么一般的简单路径问题又如何解决呢?
【例2】Formula 28
问题描述
给你一个m * n的棋盘，有的格子是障碍，要求从一个非障碍格子出发经过每个非障碍格子恰好一次，问方案总数．m, n ≤ 10．
如图，一个2 * 2的无障碍棋盘，共有4条满足要求的路径．
算法分析
确立状态：按照从上到下，从左到右依次考虑每一个格子，设(,,)
f i j S表示
转移完(i, j)这个格子，轮廓线状态为S的方案总数．如果用一般的最小表示法，不仅需要记录每个插头的连通情况，还需要额外记录每个插头是否连接了路径的一端，状态表示相当复杂．依然从括号表示法这个角度来思考如何来存储轮廓线的状态：
这个问题跟简单回路问题最大的区别为：
不是所有的插头都两两匹配，有的插头连接的
路径的另一端不是一个插头而是整条路径的一
端，我们称这样的插头为独立插头．不妨将原
来的3进制状态修改成4进制——0表示无插
头，1表示左括号插头，2表示右括号插头，3
表示独立插头，这样我们就可以用4进制完整地记录下轮廓线的信息，图中状态表示为(1203)4．
状态转移：依然设(i, j-1)的右插头为p，(i-1, j)的下插头为q，(i, j)的下插头为p'，右插头为q'．部分转移同简单回路问题完全一样，这里不再赘述，下面分三类情况讨论与独立插头有关的转移：
情况1 W(p) = 0，W(q) = 0．当前格子可能成为路径的一端，即右插头或8改编自Formula 1
下插头是独立插头，因此()
W q'← 3，()
W p'← 0．
W p'← 3，()
W q'← 0或者()
情况2 W(p) > 0，W(q) > 0，那么()
W p'← 0，()
W q'← 0
情况2.1 W(p) =3，W(q) = 3，将插头p和q连接起来就相当于形成了一条完整的路径，这种情况只能出现在最后一个非障碍格子．
情况2.2 W(p) ，W(q) 中有一个为3，如果p为独立插头，那么无论q是左括号插头还是右括号插头，与q相匹配的插头v成为了独立插头，因此，W(v) ←3．如果q为独立插头，类似处理．
情况3 W(p) ，W(q) 中有一个>0，即p, q中有一个插头存在．
情况3.1 如果这个插头为独立插头，若在最后一个非障碍格子，这个插头可以成为路径的一端，否则可以用右插头或下插头来延续这个独立插头．情况3.2 如果这个插头是左括号或右括号，那么我们以将这个插头“封住”，使它成为路径的一端，需要将这个插头所匹配的另一个插头的状态修改成为独立插头．
情况2.2, 3.2需要计算某个左括号或右括号与之匹配的括号，计算新的状态的时间复杂度为O(n)，其余情况计算新的状态的时间复杂度为O(1)．特别需要注意，任何时候轮廓线上独立插头的个数不可以超过2个．至此问题完整解决，m = n = 10的无障碍棋盘，扩展的状态总数为3493315，完全可以承受．
上面两类题目我们用括号表示法取得了很不错的效果，但是它存在一定的局限性，即插头必须满足两两匹配．那么对于更加一般的问题，一个连通分量内出现大于2个插头，上述的括号表示方法显得束手无策．下面将介绍一种括号表示法的变形，它可以适用于出现连通块内大于2个插头的问题，我们称之为广义的括号表示法：
假设一个连通分量从左到右有多个插头，不妨将最左边的插头标记为“(”，最右边的插头标记为“)”，中间的插头全部标记为“)(”，那么能够匹配的括号对应的插头连通．如果问题中可能出现一个连通分量只有一个插头，那么这个插头标记为“( )”，这样插头之间的连通性可用括号序列完整地记录下来，比如对于一个连通性状态为{1,2,2,3,4,3,2,1}，我们可以用(-(-)(-(-()-)-)-)记录．这种广义的括号表示方法需要用4进制甚至5进制存储状态，而且直接对状态连通性进行修改情况非常多，最好还是将状态进行解码，修改后再重新编码．下文我们将会运用广义的括号表示法解决一些具体的问题．
小结
本章针对一类简单路径问题，提出了一种新的状态表示方法——括号表示
法，最后提出了广义的括号表示方法．相比普通的最小表示法，括号表示法巧妙地把连通块与括号匹配一一对应，使得状态更加简单明了，虽然不会减少扩展的状态总数，但是转移开销的常数要小很多，是一个不错的方法．
三. 一类棋盘染色问题
有一类这样的问题——给你一个m * n的棋盘，要求给每个格子染上一种颜色(共k种颜色)，每种颜色的格子相互连通(4连通)．本章主要对这类问题的解法进行探讨，我们从一个例题说起：
【例3】Black & White9
问题描述
一个m * n的棋盘，有的格子已经染上黑色或白色，现在要求将所有的未染色格子染上黑色或白色，使得满足以下2个限制：
1)所有的黑色的格子是连通的，所有的白色格子也是连通的．
2)不会有一个2 * 2的子矩阵的4个格子的颜色全部相同．
问方案总数．(m, n ≤ 8)
如下图，m = 2，n = 3，灰色格子为未染色格子，共有9种染色方案．
算法分析
这是一个典型的棋盘染色问题，着色规则有：
1) 只有黑白两种颜色，即k = 2，并且同色的格子互相连通．
2) 没有同色的2 * 2的格子．
对于简单路径问题来说，相邻的格子是否连通取决于它们之间的插头是否9Source : Uva10572
存在，状态记录轮廓线上每个插头是否存在以及插头之间的连通性；而棋盘染色问题相邻的格子是否连通取决于它们的颜色是否相同，这就需要记录轮廓线上方n 个格子的颜色以及格子之间的连通性．
确立状态 设当前转移完Q(i, j)这个格子，对以后的决策产生影响的信息有：轮廓线上方n 个格子的染色情况以及它们的连通性，由第2条着色规则“没有同色的2 * 2的格子”可知P(i-1, j)的颜色会影响到(i, j+1)着色，因此我们还需
要额外记录格子P 的颜色．动态规划的状态为：
01(,,,,)f i j S S cp 表示转移完(i, j)，轮廓线上从左到
右n 个格子的染色情况为S 0 (0 ≤ S 0 < 2n )，连通性
状态为S 1，格子P 的颜色为cp(0或1)的方案总
数．
状态的精简 如果相邻的2个格子不属于同
一个连通块，那么它们必然不同色，因此只需要记录(i, 1)和(i-1, j+1)两个格子的颜色，利用S 1就可以推出n 个格子的颜色．这个精简不会减少状态的总数，仍然需要一个变量来记录两个格子的颜色，因此意义并不大，这里只是提一下．
状态转移 枚举当前格子(i, j)的颜色，计算新的状态：S 0和cp 都很容易O(1)计算出来．考虑计算S 1：轮廓线的变化相当于将记录(i-1, j)的连通性改成记录(i, j)的连通性．根据当前格子与上面的格子和左边的格子是否同色分四类情况讨论．应当注意的是如果(i, j)和(i-1, j)不同色，并且(i-1, j)在轮廓线上为一个单独的一个连通块，那么(i-1, j)以后都不可能与其他格子连通，即剩余的格子都必须染上与(i-1, j)相反的颜色，需要特殊判断．转移的时间复杂度为O(n)．计算新状态的S 1程序框架如下：
将前一个状态的S 1解码，连通性存入c[1],c[2],…,c[n]．
If (i, j) 与 (i-1, j) 不同色并且 (i-1, j) 为一个单独的连通块Then
特殊判断
Else
If (i, j) 与 (i-1, j) 和 (i, j-1) 均同色Then
For k ← 1 to n
If c[k] = c[j] Then
c [k] ← c[j-1] // 合并两个连通块
EndIf
Else
If (i, j) 与 (i-1, j) 和 (i, j-1) 均不同色Then
c[j] ← 最大可能出现的连通块标号 // (i, j) 新建一个连通块．
Else
If (i, j) 与 (i, j-1) 同色与 (i-1, j) 不同色 Then
c[j] ← c[j-1] // (i, j) 的连通性标号跟 (i, j-1)相同．
EndIf
EndIf
EndIf
EndIf
对c[] O(n)扫描，修改成最小表示，利用c[]编码计算出新的S1．
对于m = n = 8的一个全部未染色的棋盘，扩展出来的状态总数为122395，
转移需要时间为O(n)，因此总的时间复杂度为O(TotalState * n) = 979160，运行
时间<0.1s．至此问题完整解决．类似可以解决的问题还有2007年重庆市选拔赛
Rect和IPSC 2007 Delicious Cake．
扩展上面提到的是4连通问题，如果要求8连通呢?
4连通问题是两个格子至少有一条边重合为连通，而8连通问题是两个格子至少有一个顶点重合为连通，因此需要记录所有至少有一个顶点在轮廓线上的
格子的连通和染色情况，即包括(i-1, j)在内的n+1个格子．
一个优化的方向扩展的状态中无效状态的总数很大程度上决定了算法的
效率．比如Black & White中如果出现右图的状态，那么无论之后如何决策，都
不可能满足同色的格子互相连通的性质，因此它是一个
右有4个相互不嵌套10的连通块a,b,c,d，a, c同色, b, d
同色且与a, c不同色，那么这个状态为无效状态．
小结
本章介绍了解决一类棋盘染色问题的一般思路．无论染色规则多么复杂，
我们只要在基本状态即“轮廓线上方与其相连的格子的连通性以及染色情况”
的基础上，根据题目的需要在状态中增加对以后的决策可能产生影响的信息，
问题都可以迎刃而解了．
10“嵌套”的概念可以用广义的括号匹配的表示方法来理解
四. 一类基于非棋盘模型的问题
本章将会介绍一类基于非棋盘模型的连通性状态压缩动态规划问题，它虽然不具有棋盘模型的特殊结构，但是解法的核心思想又跟棋盘模型的问题有着异曲同工之处．
【例4】生成树计数11
问题描述
给你一个n个点的无向连通图，其边集为：任何两个不同的点i, j(1 ≤ i, j ≤ n)，如果|i - j| ≤ k，那么有一条无向边
算法分析
这个题给我们的第一印象是：n非常大，k却非常小．
生成树最重要的两个性质：无环，连通．那么如果按照1,2,…,n的顺序依次考虑每一个点与前面的哪些点相连，并且保证任何时候都不会出现环，最后统计所有的点全部在一个连通分量内的方案总数即为最终的答案．
在棋盘模型的问题中，我们提出了轮廓线这个概念，任何时候只有轮廓线上方与其直接相连的格子对以后的决策会产生影响．类似地我们分析一下这个问题，当我们确定了1~i的所有点的连边情况后，哪些信息对以后的决策会产生影响：1~i–k这些点与i之后的点一定没有边相连，那么对i以后的点的决策不会产生直接的影响，因此我们需要记录的仅仅是i-k+1~i这k个点的连通信息!
如下图，我们不妨也称蓝线为轮廓线，因为只有轮廓线上的点的信息会对轮廓线右边的点的决策产生直接的影响．这样我们就很容易确立状态：
11Source : Noi2007 Day2 生成树计数, Count
状态压缩 Abstract 信息学发展势头迅猛，信息学奥赛的题目来源遍及各行各业，经常有一些在实际应用中很有价值的问题被引入信息学并得到有效解决。然而有一些问题却被认为很可能不存在有效的(多项式级的)算法，本文以对几个例题的剖析，简述状态压缩思想及其应用。 Keywords 状态压缩、Hash、动态规划、递推 Content Introducti o n 作为OIers，我们不同程度地知道各式各样的算法。这些算法有的以O(logn)的复杂度运行，如二分查找、欧几里德GCD算法(连续两次迭代后的余数至多为 原数的一半)、平衡树，有的以)运行，例如二级索引、块状链表，再往上有O(n)、O(n p log q n)……大部分问题的算法都有一个多项式级别的时间复杂度上界1，我们一般称这类问题2为P (deterministic Polynomial-time)类问题，例如在有向图中求最短路径。然而存在几类问题，至今仍未被很好地解决，人们怀疑他们根本没有多项式时间复杂度的算法，NPC(NP-Complete)和NPH(NP-Hard)就是其中的两类，例如问一个图是否存在哈密顿圈(NPC)、问一个图是否不存在哈密顿圈(NPH)、求一个完全图中最短的哈密顿圈(即经典的Traveling Salesman Problem货郎担问题，NPH)、在有向图中求最长(简单)路径(NPH)，对这些问题尚不知有多项式时间的算法存在。P和NPC都是NP(Non-deterministic Polynomial-time)的子集，NPC则代表了NP类中最难的一类问题，所有的NP类问题都可以在多项式时间内归约到NPC问题中去。NPH包含了NPC和其他一些不属于NP(也更难)的问题，NPC问题的函数版本(相对于判定性版本)一般是NPH的，例如问一个图是否存在哈密顿圈是NPC的，但求最短的哈密顿圈则是NPH的，原因在于我们可以在多项式时间内验证一个回路是否真的是哈密顿回路，却无法在多项式时间内验证其是否是最短的，NP类要求能在多项式时间内验证问题的一个解是否真的是一个解，所以最优化TSP问题不是NP的，而是NPH的。存在判定性TSP问题，它要求判定给定的完全图是否存在权和小于某常数v的哈密顿圈，这个问题的解显然可以在多项式时间内验证，因此它是NP 1请注意，大O符号表示上界，即O(n)的算法可以被认为是O(n2)的，O(n p log q n)可以被认为是O(n p+1)的。2在更正式的定义中，下面提到的概念都只对判定性问题或问题的判定版本才存在(NPH除外)。Levin给出了一个适用于非判定问题的更一般的概念，但他的论文比Cook的晚发表2年。
动态规划讲解大全 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设计方法。 基本模型 多阶段决策过程的最优化问题。 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示：（看词条图） 这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。 记忆化搜索 给你一个数字三角形, 形式如下: 1 2 3 4 5 6 7 8 9 10 找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大. 无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们写出状态转移方程：f(i, j)=a[i, j] + min{f(i+1, j)，f(i+1, j + 1)} 对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环式的动态规划就不是那么
1.资源问题1 -----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2.资源问题2 ------01背包问题 F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]); 3.线性动态规划1 -----朴素最长非降子序列 F[i]:=max{f[j]+1} 4.剖分问题1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5.剖分问题2 -----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]); 6.剖分问题3 ------乘积最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 7.资源问题3 -----系统可靠性(完全背包) F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]} 8.贪心的动态规划1 -----快餐问题 F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3} 9.贪心的动态规划2 -----过河 f[i]=min{{f(i-k)} (not stone[i]) {f(i-k)}+1} (stone[i]); +贪心压缩状态 10.剖分问题4 -----多边形-讨论的动态规划 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j]; 负正 f[I,k]*g[k+1,j];} g为min 11.树型动态规划1 -----加分二叉树 (从两侧到根结点模型)
《项目计划动态管理系统》 系统分析 详细设计 深圳市伟博多媒体电脑有限公司
目录 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ §1 系统工作流程 §2 业务流程图 §3 业务分析 §4 功能设计，报表设计 §5 系统安全性及用户权限的设置 §6 系统编码 §7 系统总体数据流程图 §8 数据库设计 §9 功能模块描述
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
§1 系统工作流程 一、申请立项 1．申请工程立项和申请项目计划可以同时进行，工程立项只申请一次，项目计划申请今后每季度申请一次，但不再申请年度计划。项目计划的第一次申请作为项目立项申请。 2．申请工程立项由局项目主管部门（基建项目为规划设计院）提出的，一个工程可能包含若干项目；申请项目立项是由负责项目实施的各基层部门（分部级）进行。立项后的工程或项目都拥有一个工程编号，一个工程仅有唯一的编号，若干项目可能共用一个工程编号。 3．工程立项时，给出总投资概算、分投资概算。项目申请时，如果几个部门的项目同属于一个工程时，需要控制计划资金。实施同一工程的各基层部门的项目计划总投资之和不能超过工程概算总投资，各部门各类分项投资的和不能超过概算分投资（概算资金不严格限制）。部门项目季度计划总投资和分投资的累计值不能超过该项目计划总投资和分投资（项目投资严格限制）。 4．工程立项申请时，录入项目名称、主管部门、必要性、实施内容、建设规模、总投资、建设工期、分投资（建筑工程、安装工程、设备材料、其他）、申请日期、设备材料（名称、规格、数量、单价、总价、计算依据）；项目立项申请时录入项目名称、实施部门、必要性、实施内容、建设规模、总投资、建设工期、分投资（建筑工程、安装工程、设备材料、其他）、项目负责人信息、实施人员、申请日期，设备材料（名称、规格、
3 大规模状态空间中的动态规划和强化学习问题 本章我们将讨论大规模状态空间中的动态规划和强化学习问题。对于这类问题，我们一般很难求得问题的精确解，只能得到问题的近似解。前面章节所介绍的一些算法，如值迭代、策略迭代和策略搜索，无法直接用于这类问题。因此，本章将函数近似引入这些算法，提出三类基于函数近似的算法版本，分别是近似值迭代、近似策略迭代和近似策略搜索。本章将从理论和实例两个角度分析算法的收敛性，讨论如何获取值函数逼近器的方法，最后比较分析三类算法的性能。 3.1 介绍 第二章详细介绍了DP/RL中三类经典算法，这三类算法都需要有精确的值函数及策略表示。一般来说，只有存储每一个状态动作对回报值的估计值才能得到精确地Q值函数，同样V值函数只有存储每一个状态的回报值的估计值才能得到；精确的策略描述也需要存储每一个状态对应的动作。如果值函数中某些变量，比如某些状态动作对、状态等，存在很多个或者无穷多个潜在值（又或者这些值是连续的），那么我们就无法精确描述对应的Q值函数或者V值函数，因此，考虑将值函数和策略通过函数近似的方式来表示。由于实际应用中大部分问题都存在大规模或者连续状态空间，因此，函数近似方法是求解动态规划和强化学习问题的基础。 逼近器主要可以分为两大类：带参的和非参的。带参的逼近器主要是从参数空间到目标函数空间的映射。映射函数及参数的个数由先验知识给定，参数的值由样本数据进行调整。典型的例子是对一组给定的基函数进行加权线性组合，其中权重就是参数。相比之下，非参的逼近器通过样本数据直接得到。本质上，非参的函数逼近器也是含带参数的，只是不像带参的函数逼近器，参数的个数及参数的值直接有样本数据决定。例如，本书中所讨论的基于核函数的逼近器就是带参数的函数逼近器，它为每一个数据点定义一个核函数，并对这些核函数做加权线性组合，其中权重就是参数。 本章主要对大规模状态空间中动态规划和强化学习问题进行广泛而深入的讨论。第二章中所介绍的三类主要算法，值迭代、策略迭代和策略搜索，将与函数近似方法相结合，获得三类新的算法，分别是近似值迭代、近似策略迭代以及近似策略搜索。本章将从理论和实例两个角度讨论算法的收敛性，并对比分析三类算法的性能。关于值函数近似与策略逼近的一些其他重要问题，本章也将给予讨论。为了帮助读者更好的阅读本章的内容，图3.1给出一个本章的内容脉络图。
状态压缩dp 炮兵阵地 Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 8971 Accepted: 3169 Description 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。 Input 第一行包含两个由空格分割开的正整数，分别表示N和M； 接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。 Output 仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。 Sample Input 5 4
PHPP PPHH PPPP PHPP PHHP Sample Output 6 Source Noi 01 这道题是一道典型的状态压缩DP。 注意到每一行炮兵的摆放只和前两行有关系，便可以记录一个f数组，f[h,i,j]表示第h行的状态为st[i]，第h-1行的状态为st[j]。 现在的关键就是如何快速求f[h,i,j]。 注意到求f数组跟状态数有关，那么便优化状态。 首先是状态的存储。注意到m范围较小，便可以按行存储。对于每一行，如果一个格子放了炮兵，就看成1，否则看成0，然后记下对应数列的十进制值即可。但这样共有2^m种状态，显然太多了。注意到有很多状态其实是不可能的(即某个炮兵附近还有炮兵)，我们就可以再预处理状态时加一些判断。那么如何高效判断呢？对了，可以用位运算！ 判断过程如下： for i:=0 to 1 shl m-1 do begin if i and (i shl 1)<>0 then continue;//错一位进行判断 if i and (i shl 2)<>0 then continue;//错两位进行判断 inc(sl); st[sl]:=i; count[sl]:=calc(i);//count数组记录每个序列中1的个数 end; 解决了存储问题后，整个程序就很简单了，剩下的DP不再赘述，详见程序。贴代码：https://www.doczj.com/doc/9115520602.html,/code/view/18264/ var f:array[1..100,1..70,1..70] of integer; map:array[1..100] of integer; st,count:array[1..70] of integer; n,m,sl:integer; function calc(x:integer):integer; var sum:integer;
动态规划经典教程 引言：本人在做过一些题目后对DP有些感想，就写了这个总结： 第一节动态规划基本概念 一，动态规划三要素：阶段，状态，决策。 他们的概念到处都是，我就不多说了，我只说说我对他们的理解： 如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。 下面举个例子： 要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。 一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。 经过这个例子相信大家对动态规划有所了解了吧。 下面在说说我对动态规划的另外一个理解： 用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。 二，动态规划的适用范围 动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？ 一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件： 最优子结构（最优化原理） 无后效性 最优化原理在下面的最短路径问题中有详细的解答； 什么是无后效性呢？ 就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。 而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规划中形成的图无环的原因。 也就是说当前状态是前面状态的完美总结，现在与过去无关。。。 当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。 三，动态规划解决问题的一般思路。 拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：（1）模型匹配法： 最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。 （2）三要素法 仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同： 先确定阶段的问题：数塔问题，和走路问题（详见解题报告） 先确定状态的问题：大多数都是先确定状态的。 先确定决策的问题：背包问题。（详见解题报告） 一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。 （3）寻找规律法： 这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。 （4）边界条件法 找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。 （5）放宽约束和增加约束 这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。 第二节动态规划分类讨论
动态规划的基本概念 基本概念 设我们研究某一个过程,这个过程可以分解为若干个互相联系的阶段。每一阶段都有其初始状态和结束状态,其结束状态即为下一阶段的初始.状态。第一阶段的初始状态就是整个过程的初始状态,最后一阶段的结束状态就是整个过程的结束状态。在过程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖于其初始状态和该阶段的决策。动态规划问题就是要找出某种决策方法, 使过程达到某种最优效果。 这种把问题看作前后关联的多阶段过程称为多阶段决策过程, 可用图9.1表示。下面介绍动态规划的术语和基本概念。 (l)阶段 把所研究的过程恰当地分为若干个互相联系的相对独立过程。 (2)状态变量 用来描述系统所处状态的变量称为状态变量。通常用s k 表示第k 阶段的初始状态，则s k +1表示第k 阶段结束时(也就是第k+l 阶段开始时)过程的状态。 通常要求状态变量具有无后效性, 即过程在第k 阶段以后的变化只与该阶段结束时的状态有关, 而与系统如何到达此状态的过程无关。 (3)决策变量的状态转移方程。系统在第k 阶段中的变化过程, 通常我们并不关心，但我们希望知道该阶段的初始状态与结束状态之间的关系。我们用以影响该系统的手段，也用一个变量x k 表示，称为决策变量， 则第k 阶段结束时的状态s k +1是决策变量x k 和初始状态s k 的函数, 即 s k +1=T (s k ,x k ) (9-1) (9-1)称为状态转移方程。 (4)权函数 反映第k 阶段决策变量x k 的效益函数W k (s k ,x k ) 称为权函数。 (5)指标函数 判断整个过程优劣的数量指标称为指标函数。当第k 阶段初始状态为s k 时,设我们在此阶段及以后各阶段均采取最优策略时,所获得的效益为f k (s k ), 那么有 ))}(),,(({)(11++∈=k k k k k k D x k k s f x s W F opt s f k k (9-2) 其中opt 表示最优,按具体问题可取为max 或min , D k 是决策变量x k 的定义域;F k 是某一个函数; s k +1=T (s k ,x k ). 图9.1
信息学竞赛中的动态规划专题 哈尔滨工业大学周谷越 【关键字】 动态规划动机状态典型题目辅助方法优化方法 【摘要】 本文针对信息学竞赛（面向中学生的Noi以及面向大学生的ACM/ICPC）中的动态规划算法，从动机入手，讨论了动态规划的基本思想和常见应用方法。通过一些常见的经典题目来归纳动态规划的一般作法并从理论上加以分析和说明。并介绍了一些解决动态规划问题时的一些辅助技巧和优化方法。纵观全文可知，动态规划的关键在于把握本质思想的基础上灵活运用。 【目录】 1.动态规划的动机和基本思想 1.1.解决重复子问题 1.2.解决复杂贪心问题 2.动态规划状态的划分方法 2.1.一维状态划分 2.2.二维状态划分 2.3.树型状态划分 3.动态规划的辅助与优化方法 3.1.常见辅助方法 3.2.常见优化方法 4.近年来Noi动态规划题目分析 4.1 Noi2005瑰丽华尔兹 4.2 Noi2005聪聪与可可 4.3 Noi2006网络收费 4.4 Noi2006千年虫 附录参考书籍与相关材料
1.动态规划的动机和基本思想 首先声明，这里所说的动态规划的动机是从竞赛角度出发的动机。 1.1 解决重复子问题 对于很多问题，我们利用分治的思想，可以把大问题分解成若干小问题，然后再把各个小问题的答案组合起来，得到大问题的解答。这类问题的共同点是小问题和大问题的本质相同。很多分治法可以解决的问题（如quick_sort，hanoi_tower等）都是把大问题化成2个以内的不相重复的小问题，解决的问题数量即为∑(log2n / k)。而考虑下面这个问题： USACO 1.4.3 Number Triangles http://122.139.62.222/problem.php?id=1417 【题目描述】 考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 在上面的样例中，从7到3到8到7到5的路径产生了最大和：30。 【输入格式】 第一个行包含R(1<= R<=1000) ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。 【输出格式】 单独的一行包含那个可能得到的最大的和。 【样例输入】 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 1 【样例输出】 30 显然，我们同样可以把大问题化成小问题来解决。如样例中最底层的6就可以从次底层
[1]POJ 动态规划题目列表 容易： 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵，求平衡）, 1936,1952, 1953, 1958, 1959, 1962, 1975, 1989, 2018, 2029,2039, 2063, 2081, 2082,2181, 2184, 2192, 2231, 2279, 2329, 2336, 2346, 2353,2355, 2356, 2385, 2392, 2424, 不易： 1019,1037, 1080, 1112, 1141, 1170, 1192, 1239, 1655, 1695, 1707,1733(区间减法加并查集), 1737, 1837, 1850, 1920(加强版汉罗塔), 1934(全部最长公共子序列), 1937(计算几何), 1964(最大矩形面积，O(n)算法), 2138, 2151, 2161(烦，没写), 2178, 推荐： 1015, 1635, 1636(挺好的), 1671, 1682, 1692(优化), 1704, 1717, 1722, 1726, 1732, 1770, 1821, 1853, 1949, 2019, 2127, 2176, 2228, 2287, 2342, 2374, 2378, 2384, 2411 状态DP 树DP 构造最优解 四边形不等式 单调队列 1015 Jury Compromise 1029 False coin 1036 Gangsters 1037 A decorative fence 1038 Bugs Integrated, Inc. 1042 Gone Fishing 1050 To the Max 1062 昂贵的聘礼 1074 Parallel Expectations 1080 Human Gene Functions 1088 滑雪 1093 Formatting Text 1112 Team Them Up! 1141 Brackets Sequence 1143 Number Game 1157 LITTLE SHOP OF FLOWERS 1159 Palindrome
动态规划和贪心算法的区别 动态规划法的基本思路： 动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。此算法常用于求解某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案，消除递归过程中产生的大量重叠子问题。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 贪心算法的基本思想： 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，贪心算法所得出的解是一系列局部最优的选择。 把求解的问题分成若干个子问题，对每一子问题求解，得到子问题的局部最优解，把子问题的解局部最优解合成原来解问题的一个解。为了解决问题，需要寻找一个构成解的候选对象集合，起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。 由以上可知：在贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。并且，每一步的最优解一定包含上一步的最优解。 而在动态规划算法中，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。动态规划的关键是状态
基于连通性状态压缩的动态规划问题 长沙市雅礼中学陈丹琦 【摘要】 基于状态压缩的动态规划问题是一类以集合信息为状态且状态总数为指数级的特殊的动态规划问题．在状态压缩的基础上，有一类问题的状态中必须要记录若干个元素的连通情况，我们称这样的问题为基于连通性状态压缩的动态规划问题，本文着重对这类问题的解法及优化进行探讨和研究．本文主要从动态规划的几个步骤——划分阶段，确立状态，状态转移以及程序实现来介绍这类问题的一般解法，会特别针对到目前为止信息学竞赛中涌现出来的几类题型的解法作一个探讨．结合例题，本文还会介绍作者在减少状态总数和降低转移开销两个方面对这类问题优化的一些心得． 【关键词】 状态压缩连通性括号表示法轮廓线插头棋盘模型
【目录】 【序言】 (3) 【正文】 (5) 一. 问题的一般解法 (5) 【例1】Formula 1 (5) 问题描述 (5) 算法分析 (5) 小结 (11) 二. 一类简单路径问题 (12) 【例2】Formula 2 (15) 问题描述 (15) 算法分析 (15) 小结 (16) 三. 一类棋盘染色问题 (17) 【例3】Black & White (17) 问题描述 (17) 算法分析 (17) 小结 (19) 四. 一类基于非棋盘模型的问题 (20) 【例4】生成树计数 (20) 问题描述 (20) 算法分析 (20) 小结 (21) 五. 一类最优性问题的剪枝技巧 (22) 【例5】Rocket Mania (22) 问题描述 (22) 算法分析 (23) 小结 (25) 六.总结 (25) 【参考文献】 (26) 【感谢】 (26) 【附录】 (26)
___________项目系统动态数据 准备方案 客户项目经理： 日期： 用友项目经理： 日期： 概要 系统上线前期，需要进行静态数据和动态数据的导入。静态数据和动态数据的导入，需要 提前按照一定的规则来整理数据。整理完毕的数据，将按照上线时的导入计划估算录入（或装载）的工作量，按照约定的时间进度导入产品系统。 静态数据的准备方式，见《静态数据准备方案》。 动态数据，是一种始终处于变动中的数据。例如客户的各种单据，库存数据，财务数据等 等。 所以动态数据的准备，必须集中时间，按照一定的格式，快速整理完毕，快速导入系统, 才 可能不会影响系统的正常上线。 一般动态数据的整理，在会计期末进行。动态数据的导入，在期初进行。 例如： 客户公司在 6 月 10 日进行库存盘点准备，20 日组织人员进行一次库存盘点，27 日前完成库存动态数据准备工作，28 日到 30 日进行库存数据的录入。则库存数据为截至到27 日的库存数据。 在盘点结束，恢复正常生产后，各相关部门人员应做好生产、采购、销售订单及库存变化 单据的保存、记录，在 6 月底（用调整单开帐）或7月期初（用开帐程序开帐）库存数据录入后， 开始补录入这批单据（必要时加班进行），在系统切换后 2 天内务必完成。 二、前期工作的准备
1、库存动态数据的准备 库存动态数据，应该按照现有库存帐的实时数据进行整理归类。建议在库存数据导入系统 之前，对库存数据进行盘点，得到真实的库存数据，并导入系统。否则，库存数据不准确，整个 系统的资料信息将毫无意义。 下表为库存动态资料准备表单，客户公司需拟定更详细的库存盘点计划，保证按期完成盘 点及动态数据准备工作。 库存期初余额 仓库代号期初时间年月 料品代号料品名称批号期初数据期初辅助量期初金额现存量辅助量
动态规划基本原理 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。 要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题 如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。 各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果. 让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最短 图4-1 带权有向多段图 路径的长度(下面简称最短距离)。 我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达D点必然要经过B1和B2中的一个，所以A到D的最短距离必然等于B1到D的最短距离加上5，或是B2到D的最短距离加上2。同样的，B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2，……。 我们设G[i]为点i到点D的距离，显然G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析，
有： G[B1]=min{G[C1]+3，G[C2]+2}=5， G[B2]=min{G[C2]+7，G[C3]+4}=9， 再就有G[A]=min{G[B1]+5，G[B2]+2}=10， 所以A到D的最短距离是10，最短路径是A→B1→C2→D。 二、动态规划的术语 1．阶段 把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。 在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。 2．状态 状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。 在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。 过程的状态通常可以用一个或”一组数”来描述，称为状态变量。一般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量(多维情形)，因而用向量来代表；而且在每个阶段的状态维数可以不同。 当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。 3．无后效性 我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发
一、应用动态规划算法的动机 案例1：一家公司现有m万元，本年可投资的业务有n 项。其中，第一项业务对应的成本是C1，收益是R1；第二项业务对应的成本是C2，收益是R2……第n项业务对应的成本是C n，收益是R n。假设同种业务只能投资一次，不可重复。若每项业务对应的成本和收益已知，求该公司用m万元投资这些业务可以取得的最大收益。 显然可以用递归法来解决此问题： 设V（i，j）表示能够用j万元购买的前i项业务收益最大的子集的收益。根据V（i，j）这个最佳子集中是否包含业务i，可以得到下列递归关系式： V（i，j）= 该方程表示的是：如果第i项业务的成本C i比j小（或等于j），那么取得最大收益的方案有可能包含该项业务，至于是否包含，就看包含该业务所能取得的最大收益与不含该业务所能取得的最大收益两者中何者更大。而如果第i项业务的成本C i比j大，那就不能选择购买该项业务，也就是说取得最大收益的方案一定不包含此项业务。 当i和j有至少一项等于零时，表示该公司投资业务的资金为零或者不投资任何业务，所以其所能取得的收益一定为零，即当i=0或j=0时，V（i，j）=0，故该方程的边界条件是： 该案例目标是求出V（n，m），即用m万元购买的n项业务收益最大的子集的收益。 因此，可以得到以下递归过程（伪代码）： function V（i，j：integer）； begin if（i=0）or（j=0）then return0 else begin if j-C i>=0then Answer：=max［V（i-1，j），R i+V（i-1，j-C i）］； if j-C i<0then Answer：=V（i-1，j）； end； end； 1.记忆化搜索。上面的递归算法显然是正确的，但是它的运算速度却很慢，因为它的时间复杂度是指数级的。如果记V（i，j）的值是d［i，j］，以数组来表示，由于1≤i≤n，1≤j≤m，所以一共只有O（n×m）个d值需要计算，而在执行递归算法的时候却做了大量的重复运算。 可以这样改进这个算法： 因为V（i，j）的值一旦被计算出来就不会改变，所以在每次调用V函数之前先检查之前是否已经计算过该值，如果是，则直接从数组中读出，不必再花费时间重新进行计算，即： function V（i，j：integer）； begin if Calculated［i，j］then return d［i，j］； //此处为原来的V函数代码 d［i，j］：=Answer； Calculated［i，j］：=true； end； 2.自底向上的递推。除了上述这种改进方法，还有另外一种改进方法：可以按照一定的顺序计算所有的d值。由于计算d［i，j］需要知道d［i-1，j］和d［i-1，j-C i］，所以可以按照i~ j递增的顺序来计算d［i，j］，即： 动态规划算法在管理会计中的应用 【摘要】动态规划算法是运用状态转移解决多阶段决策的一种最优化方法。这种方法基于最优化原理，把多阶段过程转化为一系列单阶段问题，进而逐个求解，可以高效地解决许多用贪心算法或分治算法无法解决的问题。本文结合管理会计中的问题，运用运筹学、金融建模等知识，探讨了动态规划算法在管理会计中的应用。 【关键词】动态规划；管理会计；最优化原理 【中图分类号】F230【文献标识码】A【文章编号】1004-0994（2016）05-0053-3 钟方源 max｛V（i-1，j），R i+V（i-1，j-C i）｝，j-C i≥0 V（i-1，j），j-C i<0 V（0，j）=0，j≥0 V（i，0）=0，i≥0 2016.05财会月刊·53·□ 财务·会计□
1. 资源问题1 -----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2. 资源问题2 ------01背包问题 F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]); 3. 线性动态规划1 -----朴素最长非降子序列 F[i]:=max{f[j]+1} 4. 剖分问题1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5. 剖分问题2 -----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]); 6. 剖分问题3 ------乘积最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 7. 资源问题3 -----系统可靠性(完全背包) F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]} 8. 贪心的动态规划1 -----快餐问题 F[i,j]表示前i条生产线生产j个汉堡,k个薯条所能生产的最多饮料, 则最多套餐ans:=min{j div a,k div b,f[I,j,k] div c} F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3} 9. 贪心的动态规划2 -----过河 f[i]=min{{f(i-k)} (not stone[i]) {f(i-k)}+1} (stone[i]); +贪心压缩状态 10. 剖分问题4 -----多边形-讨论的动态规划 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j];
100个动规方程 1. 资源问题1-----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2. 资源问题2------01背包问题 F[I,j]:=max(f[i-1,j-v]+w,f[i-1,j]); 3. 线性动态规划1-----朴素最长非降子序列 F:=max{f[j]+1} 4. 剖分问题1-----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5. 剖分问题2-----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a); 6. 剖分问题3------乘积最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 7. 资源问题3-----系统可靠性(完全背包) F[i,j]:=max{f[i-1,j-c*k]*P[I,x]} 8. 贪心的动态规划1-----快餐问题 F[i,j,k]:=max{f[i-1,j',k']+(T-(j-j')*p1-(k-k')*p2) div p3} 9. 贪心的动态规划2----过河 f=min{{f(i-k)} (not stone) {f(i-k)}+1} (stone); +贪心压缩状态 10. 剖分问题4-----多边形-讨论的动态规划 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j]; 负正 f[I,k]*g[k+1,j];} g 为min 11. 树型动态规划1-----加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12. 树型动态规划2-----选课 (多叉树转二叉树,自顶向下模型) F[I,j]表示以i 为根节点选j 门功课得到的最大学分 f[i,j]:=max{f[t.l,k]+f[t.r,j-k-1]+c} 13. 计数问题1-----砝码称重 f[f[0]+1]=f[j]+k*w[j]; (1<=i<=n; 1<=j<=f[0]; 1<=k<=a;) 14. 递推天地1------核电站问题 f[-1]:=1; f[0]:=1; f:=2*f[i-1]-f[i-1-m] 15. 递推天地2------数的划分 f[i,j]:=f[i-j,j]+f[i-1,j-1]; 16. 最大子矩阵1-----一最大01子矩阵 f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f); 17. 判定性问题1-----能否被4整除 g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j) 18. 判定性问题2-----能否被k 整除 f[I,j±n mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n 20. 线型动态规划2-----方块消除游戏 f[i,i-1,0]:=0 f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]} ans:=f[1,m,0] 21. 线型动态规划3-----最长公共子串，LCS 问题 f[i,j]={0(i=0)&(j=0); f[i-1,j-1]+1 (i>0,j>0,x=y[j]); max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x<>y[j]); 22. 最大子矩阵2-----最大带权01子矩阵O(n^2*m) 枚举行的起始，压缩进数列，求最大字段和，遇0则清零 23. 资源问题4-----装箱问题(判定性01背包) f[j]:=(f[j] or f[j-v]); 24. 数字三角形1-----朴素の数字三角形 f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]); 25. 数字三角形2-----晴天小猪历险记之Hill 同一阶段上暴力动态规划 if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j] 26. 双向动态规划1数字三角形3 -----小胖办证 f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]) 27. 数字三角形4-----过河卒 //边界初始化 f[i,j]:=f[i-1,j]+f[i,j-1]; 28. 数字三角形5-----朴素的打砖块 f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]); 29. 数字三角形6-----优化的打砖块 f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]} 30. 线性动态规划3-----打鼹鼠’ f:=f[j]+1;(abs(x-x[j])+abs(y-y[j])<=t-t[j]) 31. 树形动态规划3-----贪吃的九头龙 32. 状态压缩动态规划1-----炮兵阵地 Max(f[Q*(r+1)+k],g[j]+num[k]) If (map and plan[k]=0) and ((plan[P] or plan[q]) and plan[k]=0) 33. 递推天地3-----情书抄写员 f:=f[i-1]+k*f[i-2] 34. 递推天地4-----错位排列 f:=(i-1)(f[i-2]+f[i-1]); f[n]:=n*f[n-1]+(-1)^(n-2); 35. 递推天地5-----直线分平面最大区域数 f[n]:=f[n-1]+n :=n*(n+1) div 2 + 1; 36. 递推天地6-----折线分平面最大区域数 f[n]:=(n-1)(2*n-1)+2*n; 37. 递推天地7-----封闭曲线分平面最大区域数 f[n]:=f[n-1]+2*(n-1) :=sqr(n)-n+2; 38 递推天地8-----凸多边形分三角形方法数 f[n]:=C(2*n-2,n-1) div n; 对于k 边形 f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3) 39 递推天地9-----Catalan 数列一般形式 1,1,2,5,14,42,132 f[n]:=C(2k,k) div (k+1);