动态规划算法的一般模式

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,从搜寻到动态规划,点击添加文本,点击添加文本,点击添加文本,点击添加文本,引例数塔问题,设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点动身，可以向左走或向右走，从根结点13动身向左、向右的路径长度可以是：,13117147，其和为52,1311121413，其和为63,假设要求从根结点开头，,请找出一条路径，使,路径之和最大,输出路,径的长度。,13,15,14,11,24,13,12,11,8,7,6,8,7,26,12,点击添加文本,点击添加文本,点击添加文本,点击添加文本,引例数塔问题,【问题分析】,1贪心法,点击添加文本,点击添加文本,点击添加文本,点击添加文本,引例数塔问题,【问题分析】,2搜寻：,点击添加文本,点击添加文本,点击添加文本,点击添加文本,引例数塔问题,【问题分析】,3动态规划：,点击添加文本,点击添加文本,点击添加文本,点击添加文本,引例数塔问题,13,15,14,11,24,13,12,11,8,7,6,8,7,26,12,点击添加文本,点击添加文本,点击添加文本,点击添加文本,动态规划的根本概念,1阶段：把所给问题的过程，恰当地分为假设干个相互联系的阶段，以便能按肯定的次序去求解。,2状态：状态表示每个阶段开头所处的自然状况和客观条件，它描述了争论问题过程中的状况。,3决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的打算或选择，从而确定下一阶段的状态，这种打算称为决策。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,动态规划的根本概念,4策略和最优策略：由全部阶段的决策组成的决策序列称为全过程策略，简称策略。在实际问题中，从决策允许集合中找出最优效果的策略称为最优策略。,5状态转移方程：状态转移方程是确定两个相邻阶段状态的演化过程。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,运用动态规划的条件,1最优化,子问题的局部最优将导致整个问题的全局最优，即问题具有最优子构造的性质。也就是说问题的一个最优解中包含着子问题的一个最优解。,2无后效性,当前阶段中的状态只能由上一个阶段中的状态转移方程得来，与其他阶段的状态没有关系，特殊是与未发生的阶段状态没有关系，这就是无后效性。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,动态规划算法的一般模式,1划分阶段：依据问题的时间或空间特征，把问题分为假设干个阶段；,2确定状态和状态变量：将问题进展到各个阶段时所处的各种状况用不同状态表示出来；,3确定决策并写出状态转移方程：一般是依据相邻两个阶段各状态之间的关系来确定决策；,4查找边界条件：给出的状态转移方程是一个递推式，必需有一个递推的边界条件；,5编写程序。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题1】拦截noi openjudge 8780,问题描述：,某国为了防范敌国的攻击，进展出一种拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕获到敌国的来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截全部的。,输入依次飞来的高度雷达给出的高度数据是不大于30000的正整数，计算这套系统最多能拦截多少。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,输入,第一行是一个整数N不超过15，表示数。,其次行包含N个整数，为依次飞来的高度雷达给出的高度数据是不大于30000的正整数。,输出,一个整数，表示最多能拦截的数。,样例输入,8,389 207 155 300 299 170 158 65,样例输出,6,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【,问题分析,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【,程序实现,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题2】乘积最大noi openjudge 8782,问题描述：,今年是国际数学联盟确定的“2023世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参与。活动中，主持人给全部参与活动的选手出了这样一道题目：,设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个局部，找出一种分法，使得这K+1个局部的乘积能够为最大。,同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：,有一个数字串：312，当N=3，K=1时会有以下两种分法：,1)3*12=36,2)31*2=62,这时，符合题目要求的结果是：31*2=62,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。,输入,程序的输入共有两行：,第一行共有2个自然数N，K6N40，1K6,其次行是一个长度为N的数字串。,输出,输出所求得的最大乘积一个自然数。保证最终答案不超过int范围,样例输入,4 2,1231,样例输出,62,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【,问题分析,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【,程序实现,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题3】最低通行费用noi openjudge 7614,问题描述：,一个商人穿过一个 N*N 的正方形的网格，去参与一个特别重要的商务活动。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1个单位时间。商人必需在(2N-1)个单位时间穿越出去。而在经过中间的每个小方格时，都需要缴纳肯定的费用。这个商人期望在规定时间内用最少费用穿越出去。请问至少需要多少费用？留意：不能对角穿越各个小方格即，只能向上下左右四个方向移动且不能离开网格。,输入,第一行是一个整数，表示正方形的宽度N(1=N 100)；,后面 N 行，每行 N 个不大于 100 的整数，为网格上每个小方格的费用。,输出,至少需要的费用.,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,样例输入,5,1 4 6 8 10,2 5 7 15 17,6 8 9 18 20,10 11 12 19 21,20 23 25 29 33,样例输出,109,提示,样例中，最小值为109=1+2+5+7+9+12+19+21+33。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【,问题分析,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【,程序实现,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题4】装箱问题noi openjudge 8785,问题描述：,有一个箱子容量为V正整数，0=v=20230，同时有n个物品0 n=30，每个物品有一个体积正整数。,要求n个物品中，任取假设干个装入箱内，使箱子的剩余空间为最小。,输入,第一行是一个整数V，表示箱子容量。,其次行是一个整数n，表示物品数。,接下来n行，每行一个正整数不超过10000，分别表示这n个物品的各自体积。,输出,一个整数，表示箱子剩余空间。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,样例输入,24,6,8,3,12,7,9,7,样例输出,0。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【,问题分析,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,【,程序实现,】,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题5】采药noi openjudge 1775,问题描述：,辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最宏大的医师。为此，他想拜四周最有威望的医师为师。医师为了推断他的资质，给他出了一个难题。医师把他带到个处处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。假设你是一个聪明的孩子，你应当可以让采到的草药的总价值最大。”,假设你是辰辰，你能完成这个任务吗？,输入,输入的第一行有两个整数T1=T=1000和M1=M=100，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间包括1和100的的整数，分别表示采摘某株草药的时间和这株草药的价值。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,输出,输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。,样例输入,70 3,71 100,69 1,1 2,样例输出,3,来源NOIP 2023,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,【例题6】最小代价子母树,问题描述：,有n堆沙子排成一排，每堆沙子有一个数量，例如：13 7 8 16 21 4 18。任意2堆相邻的沙子可以进展合并，将两堆沙子合并为一堆时，两堆沙子数量的和称为合并这两堆沙子的代价。经过不断的归并，最终将这些沙子归为一堆，而全部归并代价的和称为总代价。例如上列数，其中2种归并方案的代价为：,第1种的总代价为 20+24+25+44+69+87=267,第2种的总代价为 15+37+22+28+59+87=248,由此可见，不同的归并过程得到的总代价是不一样的。,问题：当n个数给出后，找出一种合理的归并方法，使得总代价最小。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,经典例题讲解,分析,点击添加文本,点击添加文本,点击添加文本,点击添加文本,动态规划小结,求得的一个最优解,当前阶段的决策仅受前一阶段决策的影响，并决定下一个阶段的决策,当前阶段,i,多个规划,(,决策,),当前最优决策,当前非最优决策,i,向着目标阶段不断改变,(,动态,),规划方向,目标阶段,初始阶段,动态规划,点击添加文本,点击添加文本,点击添加文本,点击添加文本,动态规划小结,动态规划和一般递推的不同点？,1递推的边界条件一般很明显，而动态规划的边界条件比较隐蔽，简洁被无视；,2一般递推的公式比较单一，而动态规划的状态转移方程具有选择性；,3一般的递推往往是用来计数或是求一个值，而动态规划往往是用来求一个最优值。,动态规划和一般递推的一样点？,无后效性和有边界条件。,点击添加文本,点击添加文本,点击添加文本,点击添加文本,课后练习推举,课堂争论及课后习题NOI题库：,习题1、最长上升子序列noi openjudge 1759,习题2、公共子序列noi openjudge 1808,习题3、最大子矩阵noi openjudge 1768,习题4、滑雪noi openjudge 90,习题5、机器安排,习题6、饥饿的奶牛,习题7、书的复制,习题8、能量项链,