C语言动态规划初步.ppt

ACM程序设计 福州大学至诚学院冯新 2020 1 9 2 第九讲 动态规划初步 2020 1 9 3 一 经典问题 数塔问题 有形如下图所示的数塔 从顶部出发 在每一结点可以选择向左走或是向右走 一直走到底层 要求找出一条路径 使路径上的值最大 2020 1 9 4 Input输入数据首先包括一个整数C 表示测试实例的个数 每个测试实例的第一行是一个整数N 1 N 100 表示数塔的高度 接下来用N行数字表示数塔 其中第i行有个i个整数 且所有的整数均在区间 0 99 内Output对于每个测试实例 输出可能得到的最大和 每个实例的输出占一行 SampleInput15738810274445265SampleOutput30 2020 1 9 5 用暴力的方法 可以吗 2020 1 9 6 这道题如果用枚举法 暴力思想 在数塔层数稍大的情况下 如31 则需要列举出的路径条数将是一个非常庞大的数目 2 30 1024 3 10 9 10亿 试想一下 2020 1 9 7 拒绝暴力 倡导和谐 2020 1 9 8 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值 只要左右两道路径上的最大值求出来了才能作出决策 同样 下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策 这样一层一层推下去 直到倒数第二层时就非常明了 如数字2 只要选择它下面较大值的结点19前进就可以了 所以实际求解时 可从底层开始 层层递进 最后得到最大值 结论 自顶向下的分析 自底向上的计算 考虑一下 2020 1 9 9 有公式 MaxSum r j a r j r N Max MaxSum r 1 j MaxSum r 1 j 1 a r j r 其他 2020 1 9 10 intmain inta 100 100 intsum 100 100 intt i j scanf d includeintmax inta intb if a b returna elsereturnb 2020 1 9 11 许多求最优解的问题可以用动态规划来解决 用动态规划解题首先要把原问题分解成若干个子问题 子问题的解一旦求出就被保存 找到子问题 就意味着找到了将整个问题逐渐分解的办法 因为子问题可以用相同的思路分解成子问题 一直分解下去 直到最底层规模最小的问题一目了然看出解 每层问题的解决 会导致上层问题的解决 逐层向上 就会导致整个问题的解决 我们可采取自底层的子问题开始 自底向上的推导出一个个子问题的解 2020 1 9 12 二 经典问题 最长有序子序列 2020 1 9 13 二 经典问题 最长有序子序列 问题描述一个数的序列bi 当b1 b2 bS的时候 我们称这个序列是上升的 对于给定的一个序列 a1 a2 aN 我们可以得到一些上升的子序列 ai1 ai2 aiK 这里1 i1 i2 iK N 比如 对于序列 1 7 3 5 9 4 8 有它的一些上升子序列 如 1 7 3 4 8 等等 这些子序列中最长的长度是4 比如子序列 1 3 5 8 你的任务 就是对于给定的序列 求出最长上升子序列的长度 2020 1 9 14 二 经典问题 最长有序子序列 输入数据输入的第一行是序列的长度N 1 N 1000 第二行给出序列中的N个整数 这些整数的取值范围都在0到10000 输出要求最长上升子序列的长度 输入样例71735948输出样例4 2020 1 9 15 二 经典问题 最长有序子序列 如何把这个问题分解成子问题呢 经过分析 发现 求以ak k 1 2 3 N 为终点的最长上升子序列的长度 是个好的子问题 这里把一个上升子序列中最右边的那个数 称为该子序列的 终点 虽然这个子问题和原问题形式上并不完全一样 但是只要这N个子问题都解决了 那么这N个子问题的解中 最大的那个就是整个问题的解 MaxLen 1 1MaxLen k Max MaxLen i 1 i k且ai ak且k 1 1MaxLen k 的值 就是在ak左边 终点 数值小于ak 且长度最大的那个上升子序列的长度再加1 因为ak左边任何 终点 小于ak的子序列 加上ak后就能形成一个更长的上升子序列 2020 1 9 16 解决方案 2020 1 9 17 include defineMAX N1000intb MAX N 10 intaMaxLen MAX N 10 intmain intN i j nMax