设有一个三角形的数塔，顶点为根结点，每个结 点有一个整数值。从顶点出发，可以向左走或向 右走，从根结点13出发向左、向右的路径长度可 以是： 13 13－11－7－14－7，其和为52 11 8 13－11－12－14－13，其和为63 • 若要求从根结点开始， 26 7 12 请找出一条路径，使 8 15 6 14 路径之和最大,输出路 24 7 13 径的长度。 12
经典例题讲解
输入 第一行是一个整数N（不超过15），表示导弹数。 第二行包含N个整数，为导弹依次飞来的高度（雷达给出的高 度数据是不大于30000的正整数）。 输出 一个整数，表示最多能拦截的导弹数。 样例输入 8 389 207 155 300 299 170 158 65 样例输出 6
经典例题讲解
经典例题讲解
【问题分析】
【程序实现】
经典例题讲解
【例题3】最低通行费用（noi openjudge 7614） 问题描述： 一个商人穿过一个 N*N 的正方形的网格，去参加一个非常重要的商务活动 。他要从网格的左上角进，右下角出。每穿越中间1个小方格，都要花费1 个单位时间。商人必须在(2N-1)个单位时间穿越出去。而在经过中间的每 个小方格时，都需要缴纳一定的费用。这个商人期望在规定时间内用最 少费用穿越出去。请问至少需要多少费用？注意：不能对角穿越各个小 方格（即，只能向上下左右四个方向移动且不能离开网格）。 输入 第一行是一个整数，表示正方形的宽度N (1 <= N < 100)； 后面 N 行，每行 N 个不大于 100 的整数，为网格上每个小方格的费用。 输出 至少需要的费用.
经典例题讲解
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。 输入 程序的输入共有两行： 第一行共有2个自然数N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为N的数字串。 输出 输出所求得的最大乘积（一个自然数）。（保证最终答案不超过int范围） 样例输入 42 1231 样例输出 62
经典例题讲解
【例题1】拦截导弹（noi openjudge 8780） 问题描述： 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但 是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能 够到达任意的高度，但是以后每一发炮弹都不能高于前一 发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系 统还在试用阶段，所以只有一套系统，因此有可能不能拦 截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于 30000的正整数），计算这套系统最多能拦截多少导弹。
动态规划算法的一般模式
• （1）划分阶段：按照问题的时间或空间特征，把 问题分为若干个阶段； • （2）确定状态和状态变量：将问题发展到各个阶 段时所处的各种情况用不同状态表示出来； • （3）确定决策并写出状态转移方程：一般是根据 相邻两个阶段各状态之间的关系来确定决策； • （4）寻找边界条件：给出的状态转移方程是一个 递推式，必须有一个递推的边界条件； • （5）编写程序。
动态规划的基本概念
• （4）策略和最优策略：由所有阶段的决策 组成的决策序列称为全过程策略，简称策 略。 在实际问题中，从决策允许集合中找 出最优效果的策略称为最优策略。 • （5）状态转移方程：状态转移方程是确定 两个相邻阶段状态的演变过程。
运用动态规划的条件
• （1）最优化 子问题的局部最优将导致整个问题的全 局最优，即问题具有最优子结构的性质。 也就是说问题的一个最优解中包含着子问 题的一个最优解。 • （2）无后效性 当前阶段中的状态只能由上一个阶段中 的状态转移方程得来，与其他阶段的状态 没有关系，特别是与未发生的阶段状态没 有关系，这就是无后效性。
【例题4】装箱问题（noi openjudge 8785） 问题描述： 有一个箱子容量为V（正整数，0<=v<=20000），同时有n个物品（0< n<=30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入 第一行是一个整数V，表示箱子容量。 第二行是一个整数n，表示物品数。 接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自 体积。 输出 一个整数，表示箱子剩余空间。
经典例题讲解
样例输入 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。
经典例题讲解
【问题分析】
【程序实现】
经典例题讲解
11
引例（数塔问题）
• 【问题分析】 （1）贪心法
引例（数塔问题）
• 【问题分析】 （2）搜索：
引例（数塔问题）
• 【问题分析】 （3）动态规划：
引例（数塔问题）
13 11 12 7 14 7 15 8 26 8 24
6 12
13
11
动态规划的基本概念
• （1）阶段：把所给问题的过程，恰当地分 为若干个相互联系的阶段，以便能按一定 的次序去求解。 • （2）状态：状态表示每个阶段开始所处的 自然状况和客观条件，它描述了研究问题 过程中的状况。 • （3）决策：决策表示当过程处于某一阶段 的某个状态时，可以作出不同的决定（或 选择），从而确定下一阶段的状态，这种 决定称为决策。
【问题分析】
【程序实现】
经典例题讲解
【例题2】乘积最大（noi openjudge 8782） 问题描述： 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数 学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一 场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加 。活动中，主持人给所有参加活动的选手出了这样一道题目： 设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找 出一种分法，使得这K+1个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312，当N=3，K=1时会有以下两种分法： 1) 3*12=36 2) 31*2=62 这时，符合题目要求的结果是：31*2=62