动态规划 陈昕昀.

Presentation on theme: "动态规划 陈昕昀."— Presentation transcript:

1 动态规划 陈昕昀

2 数字三角形问题 给定一个具有n层的数学三角形如下图，从顶至底有多条路径，每一步可沿左斜线向下或沿右斜线向下，路径所经过的数字之和为路径得分，请求出最小路径得分。 2 6 2 1 8 4

3 分析： 考虑第i层与第i+1层的关系 设f[i,j]表示第i层，第j列位置上的最小路径得分 则f[i,j]=min{f[i+1,j]，f[i+1,j+1]}+a[i,j]

4 网格路线问题 给出一个n行m列的网格，左下角坐标为（1，1），右上角坐标（n，m），一个物体从左下角开始只能沿着向上或向右的方向前进到下一个结点，问 从（1，1）出发，到（n，m）共有多少条路径？   （n，m） (1,1)

5 到每一个点的路径总条数只由到它的左边和下面的点的路径条数决定
分析： 到每一个点的路径总条数只由到它的左边和下面的点的路径条数决定 f[x][y]=f[x-1][y]+f[x][y-1]    

6 总结： 数字三角形问题——目的：求得最优解 网格路线问题——目的：统计可行解 共同点：
(1)具备有很明显的层次结构关系，把这种层次结构叫做子结构； (2)子结构间存在着递推关系； (3)通过求得子结构的值或子结构的最优值，可以获得最终的解。 定义： 当问题具备有子结构，通过求得子结构的值或子结构的最优值，而递推求得最终的解。这种解决问题的方法称之为动态规划算法。

7 动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。 1、最优子结构性质：问题的最优解所包含的子问题的解也是最优的。
2、子问题重叠性质：用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存下来，当再次需要计算已经计算过的子问题时直接查询，从而获得较高的解题效率。

8 最长公共子序列问题(LCS) 字符序列的子序列是指从给定字符序列中 随意地（不一定连续）去掉若干个字符（可 能一个也不去掉）后所形成的字符序列。给 定两序列X和Y，求它们的最长公共子序列。

9 f[i][j]记录X的前i个字符构成的串与Y 的前j个字符构成的串的LCS长度
分析： f[i][j]记录X的前i个字符构成的串与Y 的前j个字符构成的串的LCS长度 f[i][j] = if i = 0 or j = 0 = max(f[i][j-1],f[i-1][j], f[i-1][j-1]+1) if i,j>0 and xi = yj = max(f[i][j-1],f[i-1][j]) if i,j>0 and xi != yj :

10 最长上升子序列问题(LIS) 描述： 给出一个数列，要求从这个数列中找出 一个最长的子列，使得这个子列的元素是 严格单调上升的。 Sample Input： 10 Sample Output： 5

11 分析: 设f[i]表示第i位数字的最长上升子序列长 度，则f[i]值只与a[j]<a[i](j<i)对应的子 序列有关 f[i]=max{f[j](a[j]<a[i](j<i))}+1

12 上述算法复杂度为O(n^2)。 可以降低么？ 样例： 序列 上升长度 考虑最后一个7，其上升长度为5，故在一个长度为4的序列尾部。注意观察长度为4的序列，比如 ， ， 。最优序列为 。 故相同长度的子序列的有效信息是其序列中尾数最小的数。

13 建立一个数组s[k]来储存所有长度为k的最长上升子序列的最后一个数字的最小值。假如当前要求的为f[i]，则此时s[k]=min{a[j](f[j]=k,1<=j<i)}
具体算法： (1)用二分法在s[k]中寻找最大的一个k使s[k]<a[i]，让f[i]=k+1。 (2)s[f[i]]=min{s[f[i]],a[i]} 这样，使算法的复杂度下降为O(nlog2n)。

14 01背包问题 在n件物品取出若干件放在容量为m的背包 里，每件物品的重量为w1，w2，…wn，与 之相对应的价值为p1,p2,…,pn。求所能获 得的最大价值。m与wi均为整数。

15 分析： 设f[i,v]表示考虑到第i个物品，容量值为v时的最大价值 f[i,v]=max{f[i-1,v],f[i,v-w[i]]+p[i]} 可以优化吗？ 空间可以降低一维。 f[v]=max{f[v],f[v-w[i]]+p[i]}

16 for (i=1;i<=n;i++) for (v=m;v>=w[i];v--) f[v]=max(f[v],f[v-w[i]]+p[i]); 注意： v的循环顺序不能反。为什么？ 保证f[v-w[i]]为未考虑当前物品的最大价值，本题的前提是每个物品只能放一次。

17 完全背包问题 　有n种物品和一个容量为m的背包，每种物 品都有无限件可用。第i种物品的重量是 wi，价值是pi。求解将哪些物品装入背包 可使这些物品的费用总和不超过背包容量， 且价值总和最大。

18 容易想到的方程： f[v]=max{f[v-k*wi]+k*pi{0<=k*w<= v} 求解每个状态的时间不是常数，总时间复杂度超过O(nm)。 如何改进？

19 for (v=w[i];v<=m;v++) f[v]=max(f[v],f[v-w[i]]+p[i]);
for (i=1;i<=n;i++) for (v=w[i];v<=m;v++) f[v]=max(f[v],f[v-w[i]]+p[i]); 举个例子帮助理解： 设第i物品重量为2。 f[2]=max{f[2],f[0]+p[i]}此时考虑了i物品放入1次 f[4]=max{f[4],f[4-2]+p[i]}此时考虑了i物品放入2次 f[6]=max{f[6],f[6-2]+p[i]}此时考虑了i物品放入3次 ……

20 阶梯教室设备利用 题意：一间阶梯教室，n个演讲，第i个演讲起止时间分别为s[i]与e[i]。如果两个演讲时间有重叠，那么它们无法同时在阶级教室中举行。现要求在这些演讲中选择一些不重复的演讲来举行使得他们用的总时间尽可能的长，求这一最长时间。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

21 f[i]:第i个演讲举行后教室最长的使用时间。
分析： 方法一： 以演讲任务为阶段。 对演讲结束时间进行升序排列，使之有序。 f[i]:第i个演讲举行后教室最长的使用时间。 第二种方法： t:表示结束时间为i的 F[i]=max{F[i-1],F[s[t]]+(e[j]-s[j])} F[0]=0 f[i]=max{f[j]}+e[i]-s[i](1≤j≤i-1,e[j]≤s[i]) 初值:f[0]=0

22 分析: 方法二： 以时间为阶段。 f[i]:到i分钟为止教室的最长使用时间。 f[i]=max{f[s[j]]+i-s[j]}(1≤j≤n,s[j]≤i≤e[j])}

23 POJ2228 Naptime 题意：有头牛喜欢睡觉，一天被其分成了 n(3<=n<=3830)份，它可以选择至多m份 (2<=m<n)进行睡觉。每个时间段睡觉所得的 收益(非负)不同，且它每次睡觉都必须花一 份时间来入睡（算在m中，但是却没有收 益），每天被视为一个环，即如果第n份没 有在入睡或者熟睡状态，第一份时间就不能 是熟睡状态，求最大收益。

24 分析： f[i][j][k]表示前i个阶段，睡了j个时间 段，且第i个时间段没睡(k=0)或在睡(k=1)。 考虑1与n不相邻的情况 f[i][j][0]=max{f[i-1][j][0],f[i-1][j][1]} f[i][j][1]=max{f[i-1][j-1][1]+a[i],f[i-1][j-1][0]}

25 1与n相邻 枚举第一个时段算不算收益 (1)不算：ans=max{f[n][m][0],f[n][m][1]}; (2)算：第n个时间段必须睡 ans=f[n][m][1] 初值：f[1][1][1]=a[1]

26 拓展： DP类型： 区间DP 树型DP 状态压缩DP …… 优化方式： 滚动数组 单调队列优化 斜率优化

27 总结 动态规划算法设计步骤： 1、分析问题的最优解，找出最优解的性 质，并刻画其结构特征； 2、递归地定义最优值；
3、采用自底向上的方式计算问题的最优 值； 4、根据计算最优值时得到的信息，构造 最优解。

28 Thanks for Listening!