动态规划讲义

1、动态规划(Dynamic Programming)-QWZeng问题一： 有n堆不同的沙，标号从1到n，第i堆沙的单位价值为Vi，总重量为Wi。现有一个袋子，最多能承受G重量的上限，求能装入沙的最大价值是多少？问题二： 有n个物品，标号从1到n，第i个物品的价值为Vi，重量为Wi。现有一个袋子，最多能承受G重量的上限，求能装入物品的最大价值是多少？（物品不能拆分）solution问题三： 一个括号序列，只包含 ( , ) , , 四种括号，我们定义一个规范括号序列，一个规范括号序列满足以下条件：a. 一个空串是规范的b. 如果s是一个规范括号序列，那么(s) 和 s 也是规范的c. 如果a和b

2、是规范的，那么ab也是规范的d. 除以上情况外，都是不规范的 给一个括号序列（长度 =200)，问其最长的规范子序列是多长 ？ solutionDP的重要性：的重要性： a. DP占据了15%的比重 b. DP覆盖面很广，能跟各种问题结合起来考查 c. 分析问题的一种基本的有用的思维方式动态规划的基本原理动态规划的基本原理l最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。l无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前

3、的状态去影响它的未来的发展，这个性质称为无后效性。动态规划的基本步奏：动态规划的基本步奏：一： 建立状态表示二： 写出状态转移方程三： 实现(包括一些空间优化，时间优化）例子一： 爬楼梯 小Q要爬楼梯，他一次可以爬一层，也可以爬两层，问小Q爬n层楼层有多少种方式。 样例： 输入： 4输出： 5 状态：dpi 表示爬i层楼梯有dpi种方式状态转移方程： dpi = dpi-1 + dpi-2实现： dp0 = dp1 = 1;for(int i=2; i=n; i+) dpi = dpi-1 + dpi-2;dpn 即为答案引例二： 状态： dp i j 表示前i个物品总重量不超过j时可以装的最

4、大的价值 状态转移方程：dp i j = max ( dpi-1j, dpi-1 j-wi + vi ) 实现： dp00 = 0;for(int i=1; i=n; i+) for(int j=0; j=wi) dpij = max(dpij, dpi-1j-wi + vi); dpnG 即为答案int p=0; dpp0 = 0;for(int i=1; i=n; i+) for(int j=0; j=wi) dp1-pj = max(dp1-pj, dppj-wi+vi); p = 1-p;dppG 即为答案for(int i=1; i=wi; j-) dpj = max(dpj, dp

5、j-wi+vi);dpG 即为答案引例三： 状态： dp i j 表示串s(ij) 内最长的规范子序列 状态转移： dpij = max if(si, sk 配对) dpi+1k-1 + dpk+1j + 2;dpi+1 j ; 实现： bool match(int i, int j) if(si=(&sj=) | si=&sj=) return true; return false;memset(dp, -1, sizeof(dp);int dfs(int i, int j) if(i=j) return 0; if(dpij=0) return dpij; for(int

6、k=i+1; k=j; k+) if(match(i,k) dpij = max(dpij, dfs(i+1, k-1) + dfs(k+1, j) + 2); dpij = max(dpij, dfs(i+1, j); return dpij;引例三实现：实现上的技巧：实现上的技巧：一. 顺推二. 双向dp三. 空间优化顺推顺推用队列存储有效状态例比如：奇怪的电梯 有一个n层的电梯,在第i层，只能选择上ki层，或下ki层，问从A层到B层，最少的操作次数是多少？若无法到达，输出-1 状态：dp i 表示达到第i层所需的最少的操作次数状态转移方程： 逆推：dp i = min dp j + 1

7、, 对所有满足 j +kj = i 或 j-kj = i 的j 顺推：dp i + ki = min ( dp i + ki , dpi + 1); dp i - ki = min ( dp i - ki , dpi + 1);实现： 奇怪的电梯奇怪的电梯直接实现：memset(dp, 0 x3f, sizeof(dp);dpA = 0;while(true) bool flag = false; for(int i=1; i=n; i+) if(dpiinf) if(i+kidpi+1) dpi+ki = dpi + 1; flag = true; if(i-ki0 & dpi-ki

8、dpi+1) dpi-ki = dpi + 1; flag = true; if(!flag) break;用队列存储有效状态：int quemaxn, head=0, tail=0;memset(dp, 0 x3f, sizeof(dp);dpA = 0;quetail+ = A;while(tailhead) int i = quehead+; if(i+kidpi+1) dpi+ki = dpi + 1; quetail+ = i + ki; if(i-ki0 & dpi-kidpi+1) dpi-ki = dpi + 1; quetail+ = i - ki; 从状态转移方程中

9、考虑一些优化策略：从状态转移方程中考虑一些优化策略：a. 若决策涉及到区间操作，可考虑用线段树或数组数组来优化b. 若存在单调性，可利用其进行优化(如四边形定理，单调队列)例题：石子合并 有n堆石子排成一条直线，标号从1到n。第i堆石子有ai个，现对这n堆石子进行合并，每次合并只能选取相邻的两堆，合并的代价这这两堆石子的总个数。问将这n堆石子合并为一堆所需的最小的代价。样例： 输入 输出33 5 6 22dpij 表示将第i堆到第j堆直接所有石子合并为一堆所需的最小代价wij 表示从第i堆到第j堆之间的总的石子数dpij = min dpik + dpk+1j + wij , k=i &

10、; kj时间复杂度 o(n3) 令sij 为dpij 的最优决策则有单调性 si-1j = sij = sij+1时间复杂度 o(n2)建立状态的一个重要思想：建立状态的一个重要思想：在变与不变中建立状态在变与不变中建立状态例题：扑克牌 每张扑克牌由两个字符表示，第一个表示它的值，第二个表示其花色，值包括以下字符：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堆，在它们存在的情况

11、下，并且第x堆和要叠放的那一堆堆顶的扑克牌要么值相同，要么花色相同，满足这个条件才能叠放。 问能放将这n堆扑克牌叠成一堆。 输入：第一行n (1= n =52) 为扑克牌数量，接下来一行为n张扑克牌的信息 输出：如果可以叠成一堆输出YES，否则输出NOdp p i j k 表示还剩p堆时，第p堆堆顶为第i张扑克牌，第p-1堆堆顶为第j张扑克牌，第p-2堆堆顶为第k张扑克牌#define maxn 54bool dpmaxnmaxnmaxnmaxn;int n;char amaxn3;bool ok(int x, int y) return ax0=ay0 | ax1=ay1;bool dfs(

12、int p, int i, int j, int k) if(dppijk) 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; dppijk = 1; return 0;int main() scanf(%d, &n); for(int i=1; i=n; i+) scanf(%s, a+i); if(n=1)|(n=2&ok(1,2)|dfs(n,n,n-1,n-2) printf(YESn); else pri