当前位置:首页 >> 学科竞赛 >>

动态规划


1

动态规划
电子科技大学 齐朋辉

2

数字三角形
? ? ? ? ? ? 7 38 810 2744 45265 从第一层走到最后一层,每次向左下或右 下走,求路径的最大权值和。

3

解法
? 设f[i][j]表示从第i行第j个点到底部

的路径权 值和的最大值
f[i][j]= max(f[i+1][j],f[i+1][j+1]) +a[i][j]

4

如何求解
? 如果转移方程? ? 观察方程的性质 ? 因为第i行的解要由第i+1行的解得到,所以 必须从下向上转移!!

5

如何求解
? 最后一行怎么处理?
? f[i][j]=max(f[i+1][j],f[i+1][j+1])+a [i][j]

? i=n时,i+1行是非法状态 ? 边界条件,特殊处理即可。 ? i=n: f[i][j]=a[i]][j]

6

代码展示
for (int i=1; i<=n; i++)// 初始化边界 f[n][i]=a[n][i]; // 转移顺序很重要 for (int i=n-1; i>0; i--) for (int j=1; j<=i; j++) dp[i][j] = max(dp[i+1][j+1],dp[i+1][j]) + a[i][j];

7

要点
? 状态定义:如何描述一个子问题? ? 定义要明确。

? 状态转移方程:如何由子问题构造出原问 题的解? ? 边界条件、初始条件 ? 递推顺序

8

数字三角形II
1

3 2 4 10 1 4 3 2 20 ?从第一层走到最后一层,每次向左下或右下 走,求路径的最大权值和。 ?某一层可以随意跳

9

解法
? 加一维状态 ? 记f[i][j][k]为以(i,j)为顶点的子问题的解, k=1表示可以随意跳,k=0表示不能随意跳 。 ? 原问题的解即为f[1][1][1] ? 转移方程?

10

数字三角形III
1

3 2 4 10 1 4 3 2 20
?从第一层走到最后一层,每次向左下或右下 走,求路径的权值和的个位数的最大值

11

解法
? 之前的定义是否可行? ? 如何转移?
? ? ? ? f[i][j]=max{f[i+1][j],f[i+1][j+1]}+a[i][j] f[i][j]= (max{f[i+1][j],f[i+1][j+1]}+a[i][j])mod 10 f[i][j]=max{(f[i+1][j]+a[i][j]) mod 10, (f[i+1][j+1]+a[i][j]) mod 10}

12

解法
? 之前的定义是否可行? ? 记f[i][j][k]为,以(i,j)为起点走到底部,路径权 值和的个位数是否有可能等于k ? 如何转移? ? 对于每一个(i,j),枚举k,遍历所有状态即可

13

总结
? 算法设计
– 状态定义 – 状态转移(递推顺序有时很重要) – 边界条件、初始条件

? 条件
– 无后效性 – 最优子结构

14

滑雪
为了获得速度,滑雪的路径必须向下倾斜, 每次可以向上下左右4个方向滑行。区域由一 个二维数组给出,每个数字代表该点的高度 。求滑行的最长距离。 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9

15

困难?
? 能用刚才数字三角形的方法做么?
– 哪里不能? – 没有明确的依赖顺序,无法直接用递推进行转 移

? 解决办法
– 记忆化搜索

16

Fibonacci数列
? 把递归过程中的值记录下来,这样就能保 证每个值只算一次。
F[0] = F[1] = 1; for (int i = 2; i <= n; ++i) F[i] = -1; int Fib(int n) { if (F[n] != -1) return F[n]; F[n] = Fib(n-1) + Fib(n-2); return F[n]; }

17

滑雪的记忆化搜索实现

18

再次总结
? 如何利用转移方程求解
– 递推 – 递归 – 求解通项公式

? 如何看待记忆化
– 避免大量重复计算 – 简洁明了,方便理解 – 递推比较繁琐,或没有明确的依赖顺序(图)

19

经典模型

20

01背包
? 在n件物品取出若干件放在空间为V的背包 里,每件物品的体积为w1,w2……wn,与 之相对应的价值为p1,p2……pn。

21

01背包
? 定义状态f[i][j]: ? 考虑前i件物品,选的物品总体积=j的情况下价 值和的最大值 ? 转移方程: O(n*V)
f[i][j]=max(f[i-1][j], f[i-1][j-wi]+pi)

? 初始条件:f[0][0]=0, f[0][j>0]=-INF ? 答案:max(f[n][j<=V])

22

01背包
? 定义状态f[i][j]: ? 考虑前i件物品,选的物品总体积<=j的情况下 价值和的最大值 ? 转移方程:O(n*V)
f[i][j]=max(f[i-1][j],f[i-1][j-wi]+pi)

? 初始条件:f[0][j<=V]=0 ? 答案:f[n][V]

23

完全背包
? 有n种物品和一个容量为V的背包,每种物 品都有无限件可用。第i种物品的体积是w ,价值是p。求解将哪些物品装入背包可使 这些物品的体积总和不超过背包容量,且 价值总和最大。

24

完全背包
? 定义状态dp[i][j]: ? 考虑前i件物品,选的物品总体积=j的情况下价 值和的最大值 ? 转移方程: O(n*V*V/W)
dp[i][j]=max(dp[i-1][j-wi*k]+pi*k)(k>=0)

? 初始条件:dp[0][0]=0, dp[0][j>0]=-INF ? 答案:max(dp[n][j<=V])

25

多重背包
? 有n种物品和一个容量为V的背包,每种物 品都有一个数量限制l。第i种物品的体积是 w,价值是p。求解将哪些物品装入背包可 使这些物品的体积总和不超过背包容量, 且价值总和最大。

26

背包问题
? 分组背包 ? 二维背包 ? 树上的背包 ? 注:完全背包和多重背包都是可以优化到 O(n*V)的,参考《背包问题九讲》

27

LIS
? 一个数列S如果分别是已知数列的单调上升 子序列,且是所有符合此条件序列中最长 的,则S称为已知序列的最长上升子序列。 求S。

28

LIS
? 定义状态dp[i]: ? 表示以S[i]结尾的最长上升子序列的长度 ? 转移方程:O(n*n) dp[i] = max(dp[j]+1) (j<i && S[j]<S[i])

29

LIS
? 定义状态dp[S[i]]: ? 表示以S[i]结尾的最长上升子序列的长度 ? 转移方程: dp[S[i]]=max(dp[v]+1)(v<S[i]) ? 复杂度?O(n*n) ? 用线段树或者树状数组优化?O(n*logn)

30

LCS
? 一个数列S如果分别是两个已知数列A,B的 子序列,且是所有符合此条件序列中最长 的,则S称为已知序列的最长公共子序列。 求S。

31

LCS
? 定义状态dp[i][j]: ? 表示考虑A的前i位和B的前j位,最长公共子 序列的长度 ? 转移方程:O(|A|*|B|)
if(A[i]==B[j]) dp[i][j] = dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

32

几种常见的题型

33

动态规划
? 区间DP ? 按位DP ? 树形DP ? 状压DP

34

状态压缩DP
? ? ? ? ? ? ? 用二进制记录DP的状态 利用二进制运算进行转移 与,或,非,异或 与 1010 & 1100 = 1000 或 1010 | 1100 = 1110 非 ~1010 = 0101 异或 1010 ^ 1100 = 0110

35

埋雷
CDOJ 882

给一个n*m的矩阵,某些格子可以放雷 ,任意两个雷不能相邻,问有多少种放法。 Sample 23 9 111 010 n, m <= 12

36

埋雷
dp[i][j] 代表 处理到第i行,这一行上的雷的 摆放情况用j的二进制表示,的方案有多少 转移时,先用这一行的雷的状态 | 下一行的 不能放的位置的状态,取反后就是能放的位 置的状态,枚举这个状态的合法子集进行转 移。 如何判断一个子集合不合法 = 判断一个二进 制数有没有两个相邻的1

37

and
CDOJ 603

给你N个数,对于每个数输出N个数里与它相 与为0的最大的数,不存在输出0 Sample 2 16 98

98 16 N <= 100000 0 < ai < 1000000

38

and

正难则反:一个数A,取反为B,对于C, 如果A&C=0 , 则有C|B=B

39

and
对于初始的每个数dp[num[i]] = num[i] 转移 dp[i] = max(dp[i], dp[j]) j 为 i的二进制删掉 任意一个1得到的数 最后对于原来的每个数,取反后找dp的最大 值即可

40

2048
ZOJ 3802

Flappy 2048 有一个栈,最开始没东西,现 在过来了很多2,4,8,16,路过每个值的时候你 可以将其加入栈中,并得到这么多的分数, 如果栈顶的两个值相同,他们会合并成一个 新的值,为他们的和,并得到这么多的分数 。问你如何选择能使分数最大 4 2848 34 N <= 500

41

2048
N <= 500,所以栈中最大的数只有500*16 < 512 * 16 = 8192,并且都是2的幂 并且栈中只有最后一个单调递减序列有可能 被合并。 Dp[i][j] 代表,选到第i个数,栈中最后一个 单调递减序列的状态是j,能得到的最大分数 是多少 分这个数选或不选转移即可

42

按位DP-数位统计问题
? ? ? ? ? ? ? 求区间[A,B]之间满足某种性质的个数(最值) 1<=A,B<=10^18 例:求区间[A,B]间恰有K个8的数的个数 [1,100] K=2 ans=1 [1,100] K=1 ans=18 [1,100] K=0 ans=81 如果是求个数ret[A,B]=ret[1,B]-ret[1,A-1]

43

按位DP-数位统计问题
? ? ? ? ? ? ? ? ? cnt[L][K]表示长度为L且恰含K个8的数的个数 包含前导0 cnt[1][1]=1,cnt[1][0]=9; 如何计算[1,3981],K=1? 首位为1,2的数2*cnt[3][1] 前两位为30-38的数8*cnt[2][1]+1*cnt[2][0]; 前三位为390-397的数8*cnt[1][1] 前四位为3981的数cnt[0][0]; 首位为0的四位数cnt[3][1]

44

按位DP-数位统计问题
? ? ? ? 按位DP核心思想: 由高位到低位 高位取前缀,枚举当前位,低位任意取 低位任意取 ? DP预处理

45

按位DP-数位统计问题
? 如何求cnt[L][K]? ? cnt[0][0]=1;cnt[0][i]=0 (i>0) ? cnt[L][K]=cnt[L-1][K]*9+cnt[L-1][K-1];

46

Windy数
SCOI 2009

定义windy数:相邻数字的差至少是2的数, 例如10不是windy数,而13是windy数。求 给定区间中有多少windy数。区间端点范围 为 [1, 2000000000]

47

Windy数
显然这是一个按位DP 按位DP整体思想:由高位到低位 枚举当前位,高位的数取前缀,低位的数预 处理 [A,B] = [1,B] – [1,A-1] 我们先看代码

48

Windy数

49

Windy数

50

Windy数
按位DP要特别注意两个问题 calc(n)求出的答案0是否被计算在内,n是否 被计算在内 前导0 我的习惯:不计算n ans[l,r] = calc(r+1) – calc(l) 0是否计算在内完全看心情。。

51

Lucky
给定L,R,X,Y 输出[L,R]中,含有X个6,Y个8的第K大的数

1 <= L <= R <= 1e18

52

Lucky
先求出L之前的所有合法数H 然后二分,求[1,x]中恰好有K+H个合法数的x 即可

53

Bit
CF 413D

给定M, K,求一个N,使得N+1, N+2, … N + N中,二进制包含恰好K个1的数恰好有M 个 Sample (110,111,1000,1001,1010) 32

5

54

Bit
满足二分性! 对于N+1,N+2,…N+N 和N+2,N+3,…,N+N+1,N+N+2 下面的序列少了个N+1,多了2N+1和2N+2 但是如果N+1满足条件,2N+2一定也满足 条件 所以N越大越有可能满足条件,所以直接二 分然后DP

55

Beautiful number
CF 55D

求[L,R]区间内能被自己的每一位非0的数整除 的数。 例如132就是合法的 Sample 1 12 15 2

56

Beautiful number
如何记录出现了的数字?

如何记录是否能整除出现了的数字?

57

Beautiful number
dp[L][i][j] 代表,长度不超过L的数,出现过 的数字的状态为i,模2520的值为j的方案数 0 <= i < 256, 0 <= j < 2520 预处理:O(18 * 10 * 256 * 2520) 对于每一个查询,高位取前缀,枚举当前位 ,再枚举低位出现过的数字,这样就可以知 道低位模2520的合法值有哪些 查询:O(18*10*256)

58

例题选讲

59

稳住GCD
CDOJ923

? 给n个数的序列,问最多删掉多少数,使得 序列的gcd不变 ? 1 <= n <= 700 ? 1 <= ai <= 10000

60

稳住GCD
? Dp[i][j]表示考虑前i个数,当前的gcd为j, 最多可以删掉多少个数 ? 复杂度: O(700 * 10000)

61

brace

Google APAC test Round B D题

输出字典序第K小的包含n对括号的合法括号 匹配 sample 22 ()() 最小的是(()),次小的是()()

62

brace
先dp处理出长度为i,左括号比右括号多j的 合法方案数有多少种 然后对每一位,尝试放左括号,看方案数还 够不够,够就放,不够就放右括号。 最开始先判断下dp[n][0]是不是比K大

63

数字三角形IV
CDOJ 597

1 -3 2 4 -10 1 4 3 2 20 ?给一个数字三角形,可以在里面拿走一些数 ,拿走数的条件是,它左上和右上的数已经 被拿走了,问最多能拿到多少数

64

dp[i][j] 代表,在确定要选i, j这个位置的情况下 ,在前j-1列和第j列的前i行的范围内,最多能选 多少。 1 23 456 7891 12345 例如dp[3][3] 代表一定选6,在绿色区域范围内 能选到的最大和有多少

65

1 23 456 7891 12345 转移: dp[3][3] = max(dp[2][2], dp[3][2], dp[4][2], dp[5][2]) + sum[3][3] sum代表i,j这个位置上面的数的和

66

转移: dp[i][j]=max{dp[k][j-1],i-1<=k<=n}+sum[i][j] n^3?

67

Walk randomly
TCO 2014

? 在一个坐标轴上,一个人初始时在原点, 每次这个人随机的选择向左走一步(步长 为1)或者向右走一步(步长为1),求n步 之后该人走过的坐标宽度至少为k的概率 ? n <= 1000

68

Walk randomly
TCO 2014

? Dp[l][r]表示,向左走的最远位置到当前位 置的距离为l,向右走的最远位置到当前位 置的距离为r,的概率 ? Sum(dp[l][r]) (l + r == k) ? 复杂度:O(n * n)

69

Song list
? 有n首歌,要创建一个有P(P>=n)首歌的 播放列表,满足两个条件 ? 1、n首歌全部在播放列表里面 ? 2、任意两首相同的歌之间最少有m首歌 ? 求方案数 ? 1 <= n <= P <= 1000

70

Song list
? Dp[i][j]表示列表里已经有了i首歌曲,当前 有j首不同的歌 ? dp[i][j] = dp[i – 1][j – 1] * (n - (j – 1)) + dp[i – 1][j] * (j – m) (j > m) ? 答案为dp[P][n]

71

DAGE(Big Brother)
CDOJ 796

? 有n个怪兽,每个怪兽都有一个破坏值di ? 奥特曼初始的体力值H=2047 ? 每次奥特曼都随机的选择一个小怪兽并打 死,打死之后体力值变为H&di ? H=0的时候奥特曼就挂掉了 ? 求奥特曼至少打死K只小怪兽的概率 ? n<=50

72

DAGE(Big Brother)
? dp[i][j][k]为考虑前i个怪兽,打死了j只怪兽 ,体力值为k,的方案数 ? 如何统计答案 ? 枚举当前的体力值k>0,然后再枚举一个小 怪兽a[l],如果k&a[l]=0,就当做最后一个 打死的小怪兽为l ? 注意若之前已经打死了a[l],k&a[l]=k!=0

73

string
ASC 25 D

74

string
如果没有最开始的删除操作 直接用dp[i][j]代表第一个指针指在i,第二个 指针指在j的最少花费是多少即可 最开始的删除操作可以看成在指针移动的过 程中跳过了一段 跳过一段的时候可以看成先花费B跳了一格, 之后无花费跳了剩下的格子

75

string
dp[i][j][k]代表,第一个指针在i,第二个指针 在j,k代表上一个操作是否是删除一段的操 作,如果k=1,那么这次转移如果仍然使用 删除操作即不用花费。 枚举这次操作的方法转移即可

76

方老师字符串

CDOJ945

? 压缩变换这样定义:如果这个字符串长度 大于等于2,那么 ? 如果最后两个字符是两个0,将这两个0替 换为1 eg. 0100 -> 011 ? 如果最后两个字符不全是0,将这两个字符 替换为0 eg. 01010 -> 0100. ? 包含且仅包含N个0和M个1,且压缩变换 之后为G的串的个数 ? 0 <= N, M <= 10^5

77

方老师字符串
? 设dp[n][m][k=0/1]表示,使用n个0和m个 1,压缩之后为k的方案数 ? dp[n][m][0] = dp[n - 1][m][1] + dp[n][m - 1][0] + dp[n][m - 1][1] ? dp[n][m][1] = dp[n - 1][m][0] ? dp[n][m - 1][0] + dp[n][m - 1][1] = C(n + m - 1, n);

78

方老师字符串
? dp[n][m][0] = dp[n - 1][m][1] + C(n + m - 1, n) ? dp[n][m][1] = dp[n - 1][m][0]

? m为不变量,可以省掉,这样时间复杂度就 可以接受了。

79

DNA Sequences
SPOJ SAMER08D

? 给两个串,求最长公共子序列 ? 有一个额外的要求,子序列由若干个长度 不小于K的子串组成 ? K=3 A=lovxxelyxxxxx B=xxxxxxxlovely ? Ans=lovely ? |A|,|B|<=10^3, K<=100

80

DNA Sequences
? dp[i][j]=max(dp[i-1][j],dp[i][j-1]); ? if(f[i][j]==k) ? dp[i][j]=max(dp[i-k][j-k]+k,dp[i][j]); ? else if(f[i][j]>k) ? dp[i][j]=max(dp[i][j], dp[i-1][j1]+1,dp[i-k][j-k]+k);

81

Match

TC SRM 593

? 现在要把n个人分成两组S和T,进行接力比 赛。 ? 已知这n个人完成比赛的可能时间为[Ai,Bi] ? 每一组完成比赛的时间为该组所有人完成 比赛的时间和。 ? 记F(S,T)为S完成比赛时间与T完成比赛时间 的差值的最大可能值。 ? 求F(S,T)的最小值 ? 1 <= n <= 50, 1 <= ai, bi <= 10000

82

Match
? ? ? ? ? ? ? ? 设S花费的时间要比T花费的时间少 设SA = sum(ai) (i属于S) SB = sum(bi) (i属于S) TA、TB同理 ans = min(ans, TB – SA) SB – TA <= TB – SA ? SA + SB <= TA +TB ? SA + SB <= (SA + SB + TA + TB) / 2

83

Match
? (SA + SB + TA + TB) / 2为定值 ? 背包

84

DP优化
? ? ? ? ? 主要有以下几种: 单调队列优化 斜率优化 四边形不等式优化 线段树等高级数据结构优化

85

Garden
? 给一个长度为n的序列ai,删掉n-k个数, 使得剩下的k个数,构成一个单调上升序列 ,且差值也为一个单调上升序列 ? 1 <= k <= n <= 20000 ? 1 <= k <= 100

86

CDOJ 879
? 把n个数分成m组,使得所有组的 (MAX?MIN)^2加起来最小 ? 1 <= n <= 10000,1 <= m <=5000

87

Thank you


相关文章:
动态规划(DP)的使用条件
,但从空间复杂度来看,动态规划算法为 O(n2),而搜索 算法为 O(n),搜索算法反而优于动态规划算法。选择动态规划算法是因 为动态规划算法在空间上可以承受,而搜索...
4种常见的动态规划模型
(三)、区间类模型 区间类模型的动态规划, 一般是要求整段区间的最优值, 子问题一般是把区间分成两个 子区间。一般用二维数组表示状态,例如 f[i,j]表示从 i...
动态规划讲解大全(含例题及答案)
2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段 数就可能不同.描述阶段的变量称为阶段变量。在...
动态规划算法原理与应用
3.2 动态规划问题中的术语 阶段: 把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求 解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。...
动态规划算法举例分析
动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用这些子 问题带到原问题, 与分治算法的不同是,经分解得到的子问题往往是不是相互...
动态规划理论(精华)
动态规划理论(精华)_IT/计算机_专业资料。动态规划理论一.动态规划的逆向思维法动态规划是一种思维方法,没有统一的、具体的模式。动态规划可以从多方面 去考察,不...
动态规划 分类
动态规划 分类_计算机软件及应用_IT/计算机_专业资料。动态规划分类 1、背包模型 包括 0-1 背包、无限背包、有限背包、有价值背包、小数背包(贪心即可) 等,是极...
动态规划基本原理
动态规划基本原理近年来, 涉及动态规划的各种竞赛题越来越多, 每一年的 NOI 几乎都至少有一道题目需 要用动态规划的方法来解决; 而竞赛对选手运用动态规划知识的...
动态规划及其在资源分配中的应用
动态规划及其在资源分配中的应用摘要:在概述动态规划原理的基础上,提出了动态规划的数学模型建模的主要步骤,将动态规划思 想运用到求解资源分配中,并通过一个实际...
2设计动态规划算法的主要步骤为
2设计动态规划算法的主要步骤为_数学_自然科学_专业资料。2 设计动态规划算法的主要步骤为: (1)找出最优解的性质,并刻划其结构特征。 (2) 递归地定义最优值。...
更多相关标签:
动态规划算法 | 动态规划原理及应用 | 动态规划 背包问题 | 贪心算法 | 动态规划算法例题 | 动态规划法 | 2038年问题 | 动态规划 最短路径 |