[题2] 数塔
● 如下图所示的数塔，从顶部出发，在每一结点可以选择向左下走或是 向右下走，一直走到底层，要求找出一条路径，使路径上的数的和最 大。数塔层数用n表示，1<=n<=100。
[题2] 数塔
贪心法。时间上有保证，但得不到最优解。主要原因是贪心法只顾 眼前利益，不考虑长远利益。 在规定时间内得到正确结果，唯一的方法就是“动态规划”。
dpl(i，j)=min{dpl(i-1，j)+v(i，j)，dpl(i，j-1)+h(i，j)}
[题5] 机器分配
【问题描述】 总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司
若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设
备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。 分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设
下面以示意图表示动态规划的过程：所选路径为：9-12-10-18-10
注意分析时，有以下几个特点：
（1）将问题划分成了4个阶段；
（2）每个阶段均得到了“部分”的最优解，得到最优解时，需要进行条件判断；
（3）从最下面一层往顶层推导。
[题3] 棋盘路径问题
【题目简介】 有一个n*m的棋盘，左下角为（1,1），右上角为（n,m），如下图： 有一颗棋子，初始位置在（1,1），该棋子只能向右走或者向上走，问该 棋子从（1,1）到（n,m）一共有几条路径？ 输入：两个整数n和m 输出：一个数，路径总数
● 第i级台阶,可以从第i-2级台阶迈2级台阶到达,也 可以从第i-1级台阶迈1级台阶到达
上楼梯问题
● 慢在哪里？
● 重叠的问题被计算了多次！ ● 例如：计算f[5]时，f[5]=f[3]+f[4];而f[4]=f[3]+f[2], 此时，f[3]又被计算了一遍。 ● 每次计算f[i]时，都要递归到f[0]或f[1]! ● 时间复杂度变成了O(N!)
[题3] 棋盘路径问题
【题目简介】 如果使用枚举的方法，必定有很多路径被重复走过，这样，势必造 成程序运行时间的浪费，当n和m的值比较大的时候，程序很可能超时。 为了避免程序的重复运行，我们可以通过记录点（1,1）到任意一个点 （I,j）的路径总数来解决这个问题。假设F[I,j]是点(1,1)到点(I,j)(1≤i≤n, 1≤j≤m)的路径总数，因为棋子在棋盘中只能向右或者向上走，所以棋盘 中只能2个点的棋子可以走到点（I,j），即点(I,j-1)和(i-1,j)，这样，我们 就可以知道，F[I,j]必定是F[I,j-1]和F[i-1,j]的和，即
动态 规划
继续
从A 地到D 地要铺设一条煤气管道,其中需经过两级中 间站，两点之间的连线上的数字表示距离，如图所示。 问应该选择什么路线，使总距离最短？
3 2 A 4 B2 B1 3 C1 1 3 4
1
2 3 1 C2
D
动态 规划
C3
哈尔滨工程大学校ACM集训队
3
解法
C1 C1 2 A 4 B2
● ● ● ● ● ● ● ● ● ● ● [NOIP2010提高组第二题]乌龟棋(线性模型的优化) [NOIP2009普及组第四题]道路游戏(DP优化) [NOIP2008提高组第三题]传纸条(多进程DP) [NOIP2007提高组第三题]矩阵取数游戏(区间DP，高精度) [NOIP2006提高组第一题]能量项链(环形区间DP) [NOIP2006提高组第二题]金明的预算方案(依赖背包问题) [NOIP2005提高组第二题]过河(线性模型的优化) [NOIP2004提高组第三题]合唱队形(LIS问题) [NOIP2003提高组第三题]加分二叉树(区间DP) [NOIP2000提高组第二题]乘积最大(线性模型，高精度) ……
最短路径问题
● 图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的 连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到 达城市E，怎样走路程最短，最短路程的长度是多少?
[题1] 最长不下降子序列
【问题描述】 设有整数序列b1,b2,b3,…,bm，若存在 i1<i2<i3<…<in，且bi1<bi2<bi3<…<bin， 则称 b1,b2,b3,…,bm中有长度为n的不下降 序列bi1,bi2,bi3,…,bin。求序列 b1,b2,b3,…,bm中所有长度(n)最大不下降 子序列 输入：整数序列 输出：最大长度n
● 基本题型：
● 01背包 ● 完全背包 ● 多重背包
● 强化题型
● ● ● ● ● 混合背包 分组背包 二维费用背包 简单的依赖背包 多人背包
● 其它
● 部分背包(贪心可解)
3.区间模型
● 区间动规的特点
● 状态为一个区间 ● 用记忆化搜索更方便
● 典型例题
● 回文词 ● 括号序列 ● 沙子合并
B1
1 2 3
1 3 4
3
C2 C2 D
1
C3 C3
解：整个计算过程分三个阶段，从最后一个阶段开始。 第一阶段（C →D）： C 有三条路线到终点D 。
动态 规划
显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4
哈尔滨工程大学校ACM集训队
递推
(最短路线为B1→C1 →D)
划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一
次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算 过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的
解题效率。
动态规划与分治、递归、贪心的区别
● 递归算法在程序实现上直观容易，但因为子问题被重复计算，且程序背后存 在对栈的操作，速度（计算复杂度一般是指数级的）上劣于动态规划。在递 归的过程中，通过保存子问题的结果，可以减少计算量，同样是空间换时间 的思想，称作memoization算法。 ● 分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求 出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。动 态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题 可包含公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免 每次碰到时都要重复计算。这就是动态规划高效的一个原因。 ● 在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动 态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列， 即问题是否具有最优子结构性质。
算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问
题。
记忆化搜索的适用范围
● 记忆化搜索几乎适用于所有DP ● 尤其适用于状态先后顺序不明显的DP
● 初学DP的同学可以先写记忆化搜索
● 会搜索就会DP~
记忆化搜索的缺点
● 记忆化搜索虽然比O(N!)的搜索快了不少 ● 但是。。。N≤106 ● 递归的话，大约需要11M的栈空间 ● 显然这是不能承受的。。。
求解问题的两个重要性质
● 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的， 我们就称该问题具有最优子结构性质（ 即满足最优化原理 ）。最优 子结构性质为动态规划算法解决问题提供了重要线索。 ● 子问题重叠性质：在用递归算法自顶向下对问题进行求解时，每次产 生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规
3 3 3 1 A 2 3 4 B2 2 1 C3 C3 C2 C2 4
C1 C1
2
B1 1
1 3
D
第二阶段（B →C）： B 到C 有六条路线。
f2 ( B1 ) = min
动态 规划
d( B1,C1 ) + f1 (C1 ) d( B1,C2 ) + f1 (C2 ) d( B1,C3 ) + f1 (C3 )
● 怎么解决？
● 记忆化搜索
● 要计算f[i]时，如果发现之前已经计算过了，就不再计算，而是直接读取之前 计算的结果； ● 如果没有计算过，则计算后将结果保存在r[i]中，下次需要时，直接读取即可。
多阶段决策过程
● 多阶段决策过程（ multistep decision process ）是指这样一类特殊的 活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每 一个阶段都需要做出决策，全部过程的决策是一个决策序列。 ● 动态规划（dynamic programming ）算法是解决多阶段决策过程最优 化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划
F(1)
动态 规划
F(2)
F(3)
F(4)
F(5)
斐波那契
哈尔滨工程大学校ACM集训队
树
F(5)
计 算 顺 序
F(3)
F(4)
F(3)
F(2)
F(2)
F(1)
F(2)
动态 规划
F(1)
哈尔滨工程大学校ACM集训队
隐藏的算法
F(5) 树中的算法： F(3) = F(2) + F(1) F(4) = F(3) + F(2) F(4) F(3)
F[i,j]=F[i-1,j]+F[i,j-1]
【例4】街道问题
● 在下图中找出从左下角到右上角的最短路径，每步只能向右方或上 方走。
【例4】街道问题
在一般情况下，如果我们用二维数组H(i，j)和V(i，j)分别表示水平 方向和竖直方向的各路段长度，如H(1，2)表示水平方向上路口 (1，1)到 路口(1，2)的路段长度，V(1，2)表示竖值方向上路口(0，2)到路口(1，2) 的路段长度，则有公式：如
F(3) = F(2) + F(1)
F(5) = F(4) + F(3)