动态规划讲义精要.ppt

动态规划(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是规范的，那么ab也是规范的 d. 除以上情况外，都是不规范的 给一个括号序列（长度 =200)，问其最长的规范子序列是多长 ？ solution DP的重要性： a. DP占据了15%的比重 b. DP覆盖面很广，能跟各种问题结合起来考查 c. 分析问题的一种基本的有用的思维方式 动态规划的基本原理 最优性原理 作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。 无后效性原则 给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。 动态规划的基本步奏： 一： 建立状态表示 二： 写出状态转移方程 三： 实现(包括一些空间优化，时间优化） 例子一： 爬楼梯 小Q要爬楼梯，他一次可以爬一层，也可以爬两层，问小Q爬n层楼层有多少种方式。 样例： 输入： 4 输出： 5 状态：dp[i] 表示爬i层楼梯有dp[i]种方式 状态转移方程： dp[i] = dp[i-1] + dp[i-2] 实现： 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 j=0; j=G; j++) { dp[1-p][j] = dp[p][j]; if(j=w[i]) dp[1-p][j] = max(dp[1-p][j], dp[p][j-w[i]]+v[i]); } p = 1-p; } dp[p][G] 即为答案 for(int i=1; i=n; i++) { for(int j=G; j=w[i]; j--) dp[j] = max(dp[j], dp[j-w[i]]+v[i]); } dp[G] 即为答案 引例三： 状态： dp[ i ] [ j ] 表示串s(i…j) 内最长的规范子序列 状态转移： dp[i][j] = max { if(s[i], s[k] 配对) dp[i+1][k-1] + dp[k+1][j] + 2; dp[i+1][ j ]; } 实现： bool match(int i, int j) { if(s[i]==(s[j]==) || s[i]==[s[j]==]) return true; return false; } memset(dp, -1, siz