动态规划方法例题选编.ppt

动态规划方法例题;最长上升子序列问题 ;分析;找出状态转移方程;决策选优：求最长上升子序列的长度;状态转移方程;求解LIS的C++代码段;序列变化;例1 拦截导弹 ;拦截导弹;拦截导弹 样例输入输出 ;分析;状态转移方程;求解拦截导弹问题的C++代码段;例2 乘积最大 ;输入输出样例;分析：划分阶段;状态转移方程;高精度运算;01背包问题;输入输出;分析;状态转移方程;f(i,j)=max{f(i-1,j), f(i-1,j-w[i])+P(i)};主程序;例3 入学考试;输入输出格式;输入输出样例;分析;例4 开心的金明;输入输出;输入输出样例;分析;主要程序段;例5 装箱问题;输入输出样例;分析;主要代码段;收集苹果：二维的DP问题;分析;状态和状态转移方程;例6 传纸条 ;输入输出格式;样例输入输出;传纸条(甩干后);贪心;分析;地宫取宝 ;输入输出格式;输入输出样例