动态规划讲义

动态规划的基本步奏：
一： 建立状态表示 二： 写出状态转移方程
三： 实现(包括一些空间优化，时间优化）
例子一： 爬楼梯
小Q要爬楼梯，他一次可以爬一层，也可以爬两层，问小Q爬n层楼 层有多少种方式。
样例： 输入： 4 输出： 5 状态：dp[i] 表示爬i层楼梯有dp[i]种方式
状态转移方程： dp[i] = dp[i-1] + dp[i-2]
dp[i][j] 表示将第i堆到第j堆直接所有石子合并为一堆所需的最小代价 w[i][j] 表示从第i堆到第j堆之间的总的石子数 dp[i][j] = min{ dp[i][k] + dp[k+1][j] + w[i][j] }, k>=i && k<j 时间复杂度 o(n^3) 令s[i][j] 为dp[i][j] 的最优决策 则有单调性 s[i-1][j] <= s[i][j] <= s[i][j+1] 时间复杂度 o(n^2)
从状态转移方程中考虑一些优化策略： a. 若决策涉及到区间操作，可考虑用线段树或数组数组来优化 b. 若存在单调性，可利用其进行优化(如四边形定理，单调队列)
例题：石子合并 有n堆石子排成一条直线，标号从1到n。第i堆石子有ai个，现对这n堆石子 进行合并，每次合并只能选取相邻的两堆，合并的代价这这两堆石子的总个 数。问将这n堆石子合并为一堆所需的最小的代价。 样例： 输入 输出 3 3 5 6 22
奇怪的电梯 直接实现：
memset(dp, 0x3f, sizeof(dp)); dp[A] = 0; while(true) { bool flag = false; for(int i=1; i<=n; i++) { if(dp[i]<inf) { if(i+k[i]<=n && dp[i+k[i]]>dp[i]+1) { dp[i+k[i]] = dp[i] + 1; flag = true; } if(i-k[i]>0 && dp[i-k[i]]>dp[i]+1) { dp[i-k[i]] = dp[i] + 1; flag = true; } } } if(!flag) break; }
实现上的技巧：
一. 顺推 二. 双向dp 三. 空间优化
顺推
用队列存储有效状态 例比如：奇怪的电梯 有一个n层的电梯,在第i层，只能选择上ki层，或下ki层，问从A层到B层，最 少的操作次数是多少？若无法到达，输出-1
状态：dp[ i ] 表示达到第i层所需的最少的操作次数 状态转移方程： 逆推：dp[ i ] = min { dp[ j ] + 1 }, 对所有满足 j +kj = i 或 j-kj = i 的j 顺推：dp[ i + ki ] = min ( dp[ i + ki ] , dp[i] + 1); dp[ i - ki ] = min ( dp[ i - ki ] , dp[i] + 1); 实现：
学完这些该学啥？ 树形dp 状态压缩dp 数位dp 插头dp (一年之后再考虑这个吧)
再之后该怎么提升？ a. 多做题，锻炼自己的思维 b. 扩大知识面，dp俨然已成为一个工具，而使用这个工具前，必 然需要对问题本身有一个清晰的认识； 如 CF上一类压轴题经常是 dp+组合数学或数论 c. 多总结，从中提炼出一些有用的思想
实现： dp[0] = dp[1] = 1; for(int i=2; i<=n; i++) { dp[i] = dp[i-1] + dp[i-2]; } dp[n] 即为答案
引例二： 状态： dp[ i ] [ j ] 表示前i个物品总重量不超过j时可以装的最大的价值 状态转移方程：dp[ i ] [ j ] = max ( dp[i-1][j], dp[i-1][ j-w[i] ] + v[i] ) 实现： dp[0][0] = 0; for(int i=1; i<=n; i++) { for(int j=0; j<=G; j++) { dp[i][j] = dp[i-1][j]; if(j>=w[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]); } } dp[n][G] 即为答案 int p=0; dp[p][0] = 0; for(int i=1; i<=n; i++) { for(int i=1; i<=n; i++) { for(int j=G; j>=w[i]; j--) for(int j=0; j<=G; j++) { dp[j] = max(dp[j], dp[j-w[i]]+v[i]); dp[1-p][பைடு நூலகம்] = dp[p][j]; } if(j>=w[i]) dp[1-p][j] = max(dp[1-p][j], dp[p][j-w[i]]+v[i]); dp[G] 即为答案 } p = 1-p; } dp[p][G] 即为答案
solution
问题三： 一个括号序列，只包含" ( " , " ) ", " [ ", " ] " 四种括号，我们定义一 个规范括号序列，一个规范括号序列满足以下条件： a. 一个空串是规范的 b. 如果s是一个规范括号序列，那么(s) 和 [s] 也是规范的 c. 如果a和b是规范的，那么ab也是规范的 d. 除以上情况外，都是不规范的 给一个括号序列（长度 <=200)，问其最长的规范子序列是多长 ？
memset(dp, -1, sizeof(dp)); int dfs(int i, int j) { if(i>=j) return 0; if(dp[i][j]>=0) return dp[i][j]; for(int k=i+1; k<=j; k++) { if(match(i,k)) dp[i][j] = max(dp[i][j], dfs(i+1, k-1) + dfs(k+1, j) + 2); } dp[i][j] = max(dp[i][j], dfs(i+1, j)); return dp[i][j]; }
建立状态的一个重要思想：
在变与不变中建立状态
例题：扑克牌 每张扑克牌由两个字符表示，第一个表示它的值，第二个表示其花色， 值包括以下字符："2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A". 花色包括以下四种字符："S", "D", "H", "C". 现有n张扑克牌，将它们从左到右排成一排。即初始时刻有n堆扑克牌，每堆 一张。假设现在又x堆扑克牌，每次操作为：将第x堆叠放到第x-1堆或第x-3堆， 在它们存在的情况下，并且第x堆和要叠放的那一堆堆顶的扑克牌要么值相同， 要么花色相同，满足这个条件才能叠放。 问能放将这n堆扑克牌叠成一堆。 输入：第一行n (1<= n <=52) 为扑克牌数量，接下来一行为n张扑克牌的信息 输出：如果可以叠成一堆输出YES，否则输出NO dp[ p ] [ i ] [ j ] [ k ] 表示还剩p堆时，第p堆堆顶为第i张扑克牌，第p-1堆堆顶 为第j张扑克牌，第p-2堆堆顶为第k张扑克牌
#define maxn 54 bool dp[maxn][maxn][maxn][maxn]; int n; char a[maxn][3]; bool ok(int x, int y) { return a[x][0]==a[y][0] || a[x][1]==a[y][1]; } bool dfs(int p, int i, int j, int k) { if(dp[p][i][j][k]) return 0; if(p==3) return ok(i,j) && ok(i,k); if(ok(i,j)&&dfs(p-1,i,k,p-3)) return 1; if(ok(i,p-3)&&dfs(p-1,j,k,i)) return 1; dp[p][i][j][k] = 1; return 0; }
solution
DP的重要性：
a. DP占据了15%的比重
b. DP覆盖面很广，能跟各种问题结合起来考查
c. 分析问题的一种基本的有用的思维方式
动态规划的基本原理
最优性原理
作为整个过程的最优策略，它满足：相对前面决策所形成 的状态而言，余下的子策略必然构成“最优子策略”。
无后效性原则
给定某一阶段的状态，则在这一阶段以后过程的发展不受 这阶段以前各段状态的影响，所有各阶段都确定时，整个 过程也就确定了。这个性质意味着过程的历史只能通过当 前的状态去影响它的未来的发展，这个性质称为无后效性。
用队列存储有效状态：
int que[maxn], head=0, tail=0; memset(dp, 0x3f, sizeof(dp)); dp[A] = 0; que[tail++] = A; while(tail>head) { int i = que[head++]; if(i+k[i]<=n && dp[i+k[i]]>dp[i]+1) { dp[i+k[i]] = dp[i] + 1; que[tail++] = i + k[i]; } if(i-k[i]>0 && dp[i-k[i]]>dp[i]+1) { dp[i-k[i]] = dp[i] + 1; que[tail++] = i - k[i]; } }