动态规划选讲 JLU – WNJXYK 2018年8月5日

动态规划介绍 Introduction

动态规划 动态规划是针对于一类求最优解问题的算法，其核心是将一个问题 分解为形式相似若干子问题，通过不断利用子问题的最优决策求得 较高级问题的决策，最后求的原问题的最优觉得。 举一个例子，爬楼梯问题：面对一段有𝑁级台阶的楼梯，一次可以 跨{1,2,3}级台阶，问爬上第𝑁级有多少种不同的方法。 形式相似的问题：面对一段有𝑥(1≤𝑥≤𝑛)，相同要求的方案数为 𝐷𝑃[𝑥]。 利用决策求得较高级决策：𝐷𝑃[𝑥]=𝐷𝑃[𝑥−1]+𝐷𝑃[𝑥−2]+𝐷𝑃[𝑥 −3]。

DP问题的三个要素 具有相同子问题：问题能够分解出几个子问题，并且能够 通过这些子问题的答案来解决这个原问题。 具有相同子问题：问题能够分解出几个子问题，并且能够 通过这些子问题的答案来解决这个原问题。 满足最优化原理(最优子结构) ：一个最优决策的子决策也 是最优的。 无后效性：每一个问题的决策，不能够对解决其它未来的 问题产生影响。往往通过设计状态表示来消除决策的后效 性。

解题步骤 确定子问题 确定问题的状态表示 推导状态转移方程 优化状态表示与状态转移 确定初始状态与边界条件 实现！

如何学习动态规划 熟悉经典动态规划模型 了解动态规划类型 递推、树形、状态压缩、插头 了解相关动态规划优化 不断练习提升技能熟练度，努力提升人类智慧

经典动态规划例题 Classical Dynamic Programming Problem

子问题：从数塔的第i层第𝑗个元素走到数塔的底层的最大数字和是多少。（那么原问题即为从数塔的第1层第1个元素走到数塔的底层所能获得的最大数字和是多少） 状态表示：𝐷𝑃[𝑖][𝑗]表示从数塔的第𝑖层第𝑗个元素走到数塔的底层的最大数字和是多少。 状态转移方程：𝐷𝑃 𝑖 𝑗 = max 𝐷𝑃 𝑖+1 𝑗 , 𝐷𝑃 𝑖+1 𝑗+1 max 𝐷𝑃 𝑖+1 𝑗 , 𝐷𝑃 𝑖+1 𝑗+1 + 𝑛𝑢𝑚𝑏𝑒𝑟 𝑖 𝑗 。 每位置只访问一次，故时间复杂度为：𝑂( 𝑛 2 )。复杂度合理，无需优化。 数塔问题 给定一个𝑁层的数塔，公有 𝑁× 𝑁+1 2 个元素。 试问，从数塔的顶层走到数 塔的底层，每次只能走相邻 节点，所能达到的最大数字 和是多少。 http://acm.hdu.edu.cn/showproblem.php?pid=2084

最长上升子序列 子问题：从第一个元素到第𝑝个元素的序 列的最长上升子序列长度是多少。（当𝑝 =𝑛时，子问题变为原问题） 状态表示：𝐷𝑃[𝑥]表示从第一个元素到第x 个元素的最长上升子序列的大小。 状态转移方程 𝐷𝑃 𝑥 = 1+ max 1≤𝑖<𝑥, 𝑛𝑢𝑚 𝑖 <𝑛𝑢𝑚[𝑥] 𝐷𝑃[𝑖 ] 时间复杂度：𝑂( 𝑛 2 ) 给定一个长度为𝑛的序列 𝑎 1 , 𝑎 2 , …, 𝑎 𝑛 ，现在要求一 个子序列 𝑎 𝑃 1 , 𝑎 𝑝 2 , …, 𝑎 𝑝 𝑘 ， 使得 𝑎 𝑃 1 < 𝑎 𝑝 2 < …< 𝑎 𝑝 𝑘 且 𝑝 1 < 𝑝 2 <…< 𝑝 𝑘 。 试问最大的𝑘是多少。 http://acm.hdu.edu.cn/showproblem.php?pid=1950

采药问题 有𝑇秒时间，𝑁个任务。 每个任务花费 𝑡 𝑖 时间， 获得 𝑣 𝑖 的收益，问合理 利用时间的最大收益是 多少。 子问题：有𝑡的时间，完成前𝑛个任 务中的若干个的最大收益是多少。 状态表示：𝐷𝑃[𝑛][𝑡]表示使用不超 过𝑡的时间，完成前𝑛个任务中的若 干个所能获得的最大收益。 状态转移方程： 𝐷𝑃[𝑛+1][𝑡]=𝐷𝑃[𝑛][𝑡− 𝑡 𝑖 ]+ 𝑣 𝑖 时间复杂度：𝑂(𝑁𝑇) https://vijos.org/p/1104 采药问题 有𝑇秒时间，𝑁个任务。 每个任务花费 𝑡 𝑖 时间， 获得 𝑣 𝑖 的收益，问合理 利用时间的最大收益是 多少。

最长公共子序列 给定两个长度分别为 𝑛,𝑚的字符串𝐴, 𝐵，问 这两个字符串的最长 公共子序列的长度是 多少。 子问题：两个字符串的前缀 𝐴 1…𝑝 , 𝐵 1…𝑞 的 最长公共子串长度是多少。 状态表示：DP[p][q]表示两个字符串的前 缀 𝐴 1…𝑝 , 𝐵 1…𝑞 的最长公共子串长度。 状态转移方程： 𝐷𝑃[𝑖][𝑗]=max⁡{𝐷𝑃[𝑖−1][𝑗], 𝐷𝑃[𝑖][𝑗 −1], 𝐷𝑃[𝑖−1][𝑗−1] + [𝐴[𝑖]==𝐵[𝑗]]} 时间复杂度：𝑂(𝑛𝑚) http://www.joyoi.cn/problem/tyvj-1050 给定两个长度分别为 𝑛,𝑚的字符串𝐴, 𝐵，问 这两个字符串的最长 公共子序列的长度是 多少。 例如： abccd与aecd的 最长公共子序列为acd， 长度为3

区间动态规划

区间动态规划特点 原问题是询问一个区间上的某种最优决策。 某个区间的最优值可以由几个子区间的最优值合 并得到。 某个区间的最优值可以由几个子区间的最优值合 并得到。 区间可以不断地划分一直到划分为一个单点区间， 可以立即获得答案，然后我们就可以通过枚举一 个区间如何分解成子区间合并他们的最优值，然 后自下而上合并区间最优决策进行动态规划。 区间动态规划特点

石子合并 子问题：将这𝑁堆石子中第𝑖堆到第𝑗堆合并的最小代价 是多少（原问题即为将N堆石子中第1堆到第𝑁堆合并的 最小代价是多少） 状态表示：𝐷𝑃[𝑖][𝑗]表示将这𝑁堆石子中第𝑖堆到第𝑗堆合 并的最小代价。 状态转移方程： 𝐷𝑃 𝑖 𝑗 = min 𝑖≤𝑘≤𝑗 (𝐷𝑃 𝑖 𝑘 +𝐷𝑃[𝑘][𝑗]) + 𝑆𝑈𝑀 𝑖 𝑗 时间复杂度：𝑂 𝑛 3 https://vjudge.net/problem/CSU-1592 有排成一排的𝑁堆石子，现要 将石子有序的合并成一堆，规 定如下：每次只能移动相邻的 2堆石子合并，合并花费为新 合成的一堆石子的数量。求将 这𝑁堆石子合并成一堆的总花 费最小。

石子合并 Input 4 5 1 2 3 4 3 5 2 1 4 Output 19 33 DP[1 ,2]=3 DP[1 ,2]=8

区间动态规划一般代码

树形动态规划

树形动态规划基本概念 如果出现这样的问题:给一棵树，要求以最少的代价(或取得最大收益)完成给定的 操作。考虑使用 树形动态规划。 如果出现这样的问题:给一棵树，要求以最少的代价(或取得最大收益)完成给定的 操作。考虑使用 树形动态规划。 1. 确立状态: 几乎所以的问题都要保存以某结点为根的子树的情况，但是要根据 具体问题考虑是否要加维，加几维，如何加维。 2. 状态转移: 状态转移的变化比较多，要根据具体问题具体分析。 3. 算法实现: 由于树的结构，使用记忆化搜索比较容易实现。   由于模型建立在树上，即为树型动态规划，顾名思义，树型 动态规划就是在“树”的数据结构上的动态规划。 树型动态规划是建立在树上的，一般有两个方向: 1. 根---> 叶: 既根传递有用的信息给子节点，完后根得出最优解的过程。 2. 叶---> 根: 既根的子节点传递有用的信息给根，完后根得出最优解的过程。

树上距离 Input Output 5 3 2 1 1 2 3 2 1 4 3 1 4 5 1 1 给定一颗带权树，求每一个结 点到其最远结点的距离是多少。

数位动态规划

数位动态规划概念 有这样一类问题:求给定区间中，满足给定条件的某个 D 进制数或此 类数的数量。 所求的限定条件往往与数位有关，例如数位之和、指定数码个数、 数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素 的方法求解。此时，我们就需要利用数位的性质，设计 log(n) 级别 复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。 1. 状态确定:我们需要根据题目的要求合理地确定能够完整 表示数位 信息的状态 2. 状态转移:枚举每一位，用记忆化搜索来实现动态规划的过程。

状态压缩动态规划

状态压缩动态规划 一些题目，它们具有 DP 问题的特性，但是状态中所包含的 信息过 多，如果要用数组来保存状态的话需要四维以上的数组。 于是，我 们就需要通过状态压缩来保存状态，而使用状态压缩来 保存状态的 DP 就叫做状态压缩 DP。 我们可以把我们需要的若干信息压入一个 int 内部，通常的状态压缩 DP 是将若干了 01 状态压缩 状态压缩 DP 的特点:状态中的某一维会比较小，一般不会超过 15， 多了的话状态数会急剧上升而无法压缩，一般来说需要状态压缩的 也就是这一维。

前置技能：位运算 (x>>i)&1 去x的第i位 x|(1<<i) 给x第i为设置为1 (x|(1<<j))^(1<<j) 将x的第i位设置为0 x&-x 获得x的lowbit __builtin_popcount(x) x中1的个数 __builtin_ctz(x) x中最后一个1后面有多少0

动态规划优化

各种玄学优化方法 线段树查询最值优化 DP http://acm.hdu.edu.cn/showproblem.php?pid=5324 朴素 DP 方程:𝐷𝑃[𝑖]=max⁡{𝐷𝑃[𝑗]+1},𝑗 <𝑖,𝐿𝑗 ≥𝐿𝑖,𝑅𝑗 ≤𝑅𝑖 受限于题目的形式，这题必须使用 CDQ 分治消除一维无序 影响 + 线段树快速查 找最值 当然如果在某些限制条件少的题目里，这样的形式在某些情 况下还可以用 单调队列优化成 O(n) 线段树合并优化 DP http://codeforces.com/contest/750/problem/E 有一个长度为 n 的数字串，给你 q 个询问，每个询问 [l,r]， 问这个区间内的字符 串，经过多少次变换可以使其只存在 2017 的子序列，不存在 2016 的子序列。 DP 转移方法符合卷积过程，使用 FFT+CDQ 分治将 O(N2)DP 优化到 O(nLogn)

Coda Thanks