提高篇——动态规划专题ppt课件.ppt

提高篇 动态规划专题 1 动态规划 递归递推 一种精妙的算法思想 特点 没有固定的写法具体问题具体分析需要 多练习 多思考 多总结 什么是动态规划 最优化问题 1 复杂问题 2 分解子问题 3 记录每个解 4 DynamicProgramming 动态规划是一种用来解决一类最优化问题的算法思想 将一个复杂的问题分解成若干个子问题 通过综合子问题的最优解来得到原问题的最优解 动态规划会将每个求解过的子问题的解记录下来 这样可以提高计算效率 但不能说这种做法就是动态规划的核心 动态规划的递归写法 理解 如何记录子问题的解 来避免下次遇到相同的子问题时的重复计算 斐波那契数列 F0 1 F1 1 Fn Fn 1 Fn 2 n 2 intF intn if n 0 n 1 return1 elsereturnF n 1 F n 2 一般可以使用递归或者递推的写法来实现动态规划 其中递归写法在此处又称作记忆化搜索 缺点 重复计算 当n 5时 F 5 F 4 F 3 接下来计算F 4 F 3 F 2 这样F 3 就被计算了两次 如果n很大 时间复杂度会高达O 2n 避免重复计算 开一个一维数组dp 用于保存已经计算过的结果 其中dp n 记录F n 的结果 并用dp n 1表示F n 当前还没有被计算过 intdp maxn intF intn if n 0 n 1 return1 递归边界if dp n 1 returndp n 已经计算过 直接返回结果 不再重复计算else dp n F n 1 F n 2 计算F n 并保存至dp n returndp n 返回F n 的结果 记忆化搜索 时间复杂度O 2n 降到了O n 时间复杂度对比图 斐波那契数列递归图O 2n 斐波那契数列记忆化搜索O n 重叠子问题 OverlappingSubproblems 如果一个问题可以被分解为若干个子问题 且这些子问题会重复出现 那么就称这个问题拥有重叠子问题 一个问题必须拥有重叠子问题 才能使用动态规划去解决 动态规划的递推写法 动态规划的递推写法 如果开一个二维数组f 其中f i j 存放第i层的第j个数字 那么就有f 1 1 5 f 2 1 8 f 2 2 3 f 3 1 12 f 5 4 9 f 5 5 4 如果尝试穷举所有路径 然后记录路径上的数字和的最大值 那么由于每层中的每个数字都会有两条分支路径 因此时间复杂度为O 2n 这在n很大的情况下是不可以接受的 那么 产生这么大复杂度的原因是什么 从5出发 按5 8 7的路线来到7 并枚举从7出发的到达最底层的所有路径 但是 之后当按5 3 7的路线再次来到7时 又会去枚举从7出发的到达最底层的所有路径 这就导致了从7出发的到达最底层的所有路径都被反复地访问 其实 可以把路径上能产生的最大和记录下来 这样就可以避免重复计算 所以令dp i j 表示从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和 例如dp 3 2 就是7的最大和 那么dp 1 1 就是最终答案 现在想办法求出它 注意一个细节 如果要求出 从位置 1 1 到达最底层的最大和 dp 1 1 那么一定要先求出它的两个子问题 从位置 2 1 到达最底层的最大和dp 2 1 和 从位置 2 2 到达最底层的最大和dp 2 2 即进行了一次决策 走数字5的左下还是右下 于是dp 1 1 就是dp 2 1 和dp 2 2 的较大值加上5 公式 dp 1 1 max dp 2 1 dp 2 2 f 1 1 动态规划的递推写法 归纳 如果要求出dp i j 那么一定要求出它的两个子问题 从位置 i 1 j 到达最底层的最大和dp i 1 j 和 从位置 i 1 j 1 到达最底层的最大和dp i 1 j 1 即进行了一次决策 走位置 i j 的左下还是右下 公式 dp i j max dp i 1 j dp i 1 j 1 f i j 把dp i j 称为问题的状态 公式称为状态转移方程 它把状态dp i j 转移为dp i 1 j 和dp i 1 j 1 可以发现 状态dp i j 只与第i 1层的状态有关 而与其他层的状态无关 那么如果总是将层号增大 什么时候会到头呢 其实 数塔的最后一层的dp值总是等于元素本身 即dp n j f n j 1 j n 把这种可以直接确定其结果的部分称为边界 而动态规划的递推写法总是从这些边界出发 通过状态转移方程扩散到整个dp数组 这样就可以从最底层各位置的dp值开始 不断往上求出每一层各位置的dp值 最后就会得到dp 1 1 即为想要的答案 动态规划的递推写法 代码 include includeusingnamespacestd constintmaxn 1000 intf maxn maxn dp maxn maxn intmain intn cin n for inti 1 i f i j 输入数塔 for intj 1 j 1 i for intj 1 j i j dp i j max dp i 1 j dp i 1 j 1 f i j 动态转移方程 cout dp 1 1 endl return0 动态规划的递推写法 输入数据55831271641011695394 输出结果44 动态规划的递推写法 对比递归和递推写法 递归也可实现 即从dp 1 1 开始递归 直至到达边界时返回结果 是自顶向下 Top downApproach 即从目标问题开始 将它分解成子问题的组合 直到分解至边界为止 递推是从底向上 Bottom upApproach 即从边界开始 不断向上解决问题 直到解决了目标问题 概念 如果一个问题的最优解可以由其子问题的最优解有效地构造出来 那么称这个问题拥有最优子结构 OptimalSubstructure 可以使用动态规划的条件 一个问题必须拥有重叠子问题和最优子结构 才能使用动态规划去解决 分治与动态规划 相同点 将问题分解为子问题 然后合并子问题的解得到原问题的解 不同点 分治的子问题不重叠 动态规划的问题拥有重叠子问题 例如 归并排序和快速排序都分别处理左序列和右序列 然后将左右序列的结果合并 过程中不出现重叠子问题 因此他们使用的都是分治法 另外 分治法解决的问题不一定是最优化问题 而动态规划解决的问题一定是最优化问题 贪心与动态规划 相同点 要求原问题必须有最优子结构 不同点 贪心法的计算方式 自顶向下 但并不等待子问题求解完毕后再选择使用哪一个 而是通过一种策略直接选择一个子问题去求解 没被选择的子问题直接抛弃 这种所谓 最优选择 的正确性需要用归纳法证明 而动态规划不管是采用自底向上还是自顶向下的计算方式 都是从边界开始向上得到目标问题的解 即考虑所有子问题 贪心 壮士断腕的决策 只要选择 绝不后悔 动态规划 要看哪个选择笑到最后 暂时领先说明不了问题 最大连续子序列和 问题描述 给定一个数字序列A1 A2 An 求i j 1 i j n 使得Ai Aj最大 输出这个最大和 样例 输入 211 413 5 2输出 20 步骤1 令状态dp i 表示以A i 作为末尾的连续序列的最大和 A i 必须作为末尾 那么dp 0 2dp 1 11dp 2 7 11 4 7 dp 3 20 11 4 13 20 dp 4 15 11 4 13 5 15 dp 5 13 11 4 13 5 2 13 于是转换成求dp 0 dp 1 dp n 1 中的最大值 想办法求解dp数组 原序列 211 413 5 2 步骤2 因为dp i 以A i 结尾的连续序列 那么只有两种情况 这个最大和的连续序列只有一个元素 即A i dp i A i 这个最大和的连续序列有多个元素 即从前面某处A p 开始 p i 一直到A i 结尾 dp i dp i 1 A i 状态转移方程 dp i max A i dp i 1 A i 边界dp 0 A 0 从小到大枚举i 即可得到整个dp数组 include include include includeusingnamespacestd constintmaxn 10010 intA maxn dp maxn A i 存放序列 dp i 存放以A i 结尾的连续序列的最大和intmain intn scanf d for inti 1 idp k k i printf d n dp k cout dp k endl system pause return0 状态的无后效性 当前状态记录了历史信息 一旦当前状态确定 就不会再改变 且未来的决策只能在已有的一个或若干个状态的基础上进行 历史信息只能通过已有的状态去影响未来的决策 即每次计算状态dp i 都只会设计dp i 1 而不直接用到dp i 1 蕴含的历史信息 动态规划核心 对动态规划可解的问题来说 总会有很多设计状态的方式 但并不是所有状态都具有无后效性 因此必须设计一个拥有无后效性的状态以及相应的状态转移方程 否则动态规划就没有办法得到正确结果 事实上 如何设计状态和状态转移方程 才是动态规划的核心 而它们也是动态规划最难的地方 问题A 最大连续子序列 时间限制 1Sec内存限制 32MB 题目描述给定K个整数的序列 N1 N2 NK 其任意连续子序列可表示为 Ni Ni 1 Nj 其中1 i j K 最大连续子序列是所有连续子序列中元素和最大的一个 例如给定序列 2 11 4 13 5 2 其最大连续子序列为 11 4 13 最大和为20 现在增加一个要求 即还需要输出该子序列的第一个和最后一个元素 输入测试输入包含若干测试用例 每个测试用例占2行 第1行给出正整数K K 10000 第2行给出K个整数 中间用空格分隔 每个数的绝对值不超过100 当K为0时 输入结束 该用例不被处理 输出对每个测试用例 在1行里输出最大和 最大连续子序列的第一个和最后一个元素 中间用空格分隔 如果最大连续子序列不唯一 则输出序号i和j最小的那个 如输入样例的第2 3组 若所有K个元素都是负数 则定义其最大和为0 输出整个序列的首尾元素 样例输入5 39 25 43 2 3 10样例输出12950 2 1 提示 较难 首先可以想到的做法是枚举每个区间的和 预处理sum i 来表示区间 1 i 的和之后通过减法我们可以O 1 时间获得区间 i j 的和 因此这个做法的时间复杂度为O n 2 然后这题的数据范围较大 因此还需作进一步优化才可以AC 记第i个元素为a i 定义dp i 表示以下标i结尾的区间的最大和 那么dp i 的计算有2种选择 一种是含有a i 1 一种是不含有a i 1 前者的最大值为dp i 1 a i 后者的最大值为a i 而两者取舍的区别在于dp i 1 是否大于0 最长不下降子序列 LIS 问题描述 在一个数字序列中 找到一个最长的子序列 可以不连续 使得这个子序列是不下降 非递减 的 样例 输入 8123 1 279输出 5 长度 即12379 令dp i 表示以A i 结尾的最长不下降子序列长度 和最大连续子序列和问题一样 以A i 结尾是强制的要求 这样对A i 俩说就会有两种可能 1 如果存在A i 之前的元素S j jdp i 即把A i 跟在以A j 结尾的LIS后面时能比当前以A i 结尾的LIS长度更长 那么就把A i 跟在以A j 结尾的LIS后面 形成一条更长的不下降子序列 令dp i dp j 1 2 如果A i 之前的元素都比A i 大 那么A i 就只好自己形成一条LIS 但是长度为1 即这个子序列里面只有一个A i 最后以A i 结尾的LIS长度就是 1 2 中能形成的最大长度 状态转移方程 dp i max 1 dp j 1 j 1 2 i 1 A j A i 其中隐含了边界 dp i 1 1 i n 时间复杂度O n2 include includeusingnamespacestd constintN 100 intA N dp N intmain intn cin n for inti 1 i A i intans 1 记录最大的dp i for inti 1 i A j 状态转移方程 用以更新dp i ans max ans dp i cout ans endl return0 问题A 最长上升子序列 2Sec64MB 题目描述一个数列ai如果满足条件a1 a2 aN 那么它是一个有序的上升数列 我们取数列 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 现在你要写一个程序 从给出的数列中找到它的最长上升子序列 输入输入包含两行 第一行只有一个整数N 1 N 1000 表示数列的长度 第二行有N个自然数ai 0 ai 10000 两个数之间用空格隔开 输出输出只有一行 包含一个整数 表示最长上升子序列的长度 样例输入71735948 样例输出4 最长公共子序列 LCS 给定两个字符串 或数字序列 A和B 求一个字符串 使得这个字符串是A和B的最长公共部分 子序列可以不连续 样例 如样例所示 字符串 sadstory 与 adminsorry 的最长公共子序列为 adsory 长度为6 令dp i j 表示字符串A的i号位和字符串B的j号位之前的LCS长度 下标从1开始 如dp 4 5 表示 sads 与 admin 的LCS长度 那么可以根据A i 和B j 的情况 分为两种决策 1 若A i B j 则字符串A与字符串B的LCS增加了1位 即有dp i j dp i 1 j 1 1 2 若A i B j 则字符串A的i号位和字符串B的j号位之前的LCS无法延长 因此dp i j 将会继承dp i 1 j 与dp i j 1 中的较大值 即有dp i j max dp i a j dp i j 1 状态转移方程 边界 dp i 0 dp 0 j 0 0 i n 0 i m 时间复杂度 O nm 输入数据 sadstoryadminsorry 输出结果 6 最长回文子串 给出一个字符串S 求S的最长回文子串的长度 样例 字符串 PATZJUJZTACCBCC 的最长回文子串为 ATZJUJZTA 长度为9 最长回文子串 是否能转换为最长公共子序列 LCS 来求解 把字符串S倒过来变成字符串T 然后对S和T进行LCS模型求解 得到的结果就是需要的答案 一旦S中同时存在一