本蒟蒻最近忙于切题, 不会的题大多数来源于动态规划, 虽然动态规划的思想貌似挺简单, 但是想出来比较难。

如何你不了解什么是动态规划? 请移步<<算法导论>>第15章.

如何解决一个动态规划问题呢? 我认为最重要的是找出问题的最优子结构. 动态规划的思想就是将一个问题分解为若干个子问题，再通过子问题的最优解构造出问题的最优解。

证明问题具有最优子结构

最常用的方法是反证法, 我们来看看(0-1)背包问题是怎么证明的?

(0-1)背包问题可以归纳为在有限个可供选择的方案中，寻找满足一定约束的最好方案, 这实际上就是一个整数规划问题

我们下面来证明这个问题具有最优子结构, 也就是它的解包括子问题的最优解

假设我们已经找到了一组最优解(y1,y2....yn), 我们先将问题的规模缩小一下, 那么我们可以推出(y2, y3 ... yn)是下面子问题的最优解:

假设(z2, z3, ... , zn)是上面子问题的最优解, 即(y2, y3,... yn)不是该子问题的最优解, 这样我们就假设了该问题不具有最优子结构了.

继续得出

说明(y1,z2,z3,⋯,zn)是比(y1,y2,y3,⋯,yn)更优的一个解，与原假设(y1,y2,y3,⋯,yn)是问题的最优解矛盾!

因此, 我们证明了该问题具有最优子结构, 这个方法其实来自于<<算法导论>>里介绍的"剪贴法", 我们就可以通过子问题的最优解来构造出原问题的最优解惹!

例题

接下来我们来看一波题,

(洛谷P1280 尼克的任务)： https://www.luogu.com.cn/problem/P1280

我们先来简单地证明一下这个问题的最优子结构, 为了提高体验避免满屏幕数学符号，这里用不太严谨的方式证明。

和背包问题的证明方法一样, 假设我们得到了该问题的一组最优解, 也就是题目中所说的能获得最大摸鱼时间的任务组(y1, y2,...yn), 我们尝试将问题规模缩小, 把工作时间缩小为n-1, 这个子问题的解为(y1, y2,...yn-1) (这里不太严谨, 因为如果最后一组工作的开始时间<=n-完成该工作的时间, 那么该问题的解还是(y1, y2, ... , yn))

我们还是老套路, 假设(z1, z2, ... , zn-1)是该子问题的最优解, 则(y1, y2, ..., yn-1)不是该子问题的最优解. 这样我们可以推出选择(z1, z2, ... , zn-1)时工作时间会更短, 于是(z1, z2, ... , zn)是该问题的最优解, 而(y1, y2, ..., yn) 不是, 与假设产生矛盾! 于是这个问题的最优子结构得证!

根据最优子结构间的关系推出最优解

证明了问题的最优子结构, 只是解决这个问题的一小步, 我们还要找出各个子问题间的关系， 并利用这些子问题来构造出原问题的一个最优解!

一般地, 我们用dp数组(dp table)来保存子问题的结果, 所以定义dp的含义以及如何优化子问题的空间(是二维数组或是多维数组?)是十分重要的。

回到上题, 我们可以定义dp[i] : 在第i时刻的最大空闲时间。 通过观察可得, 最后结果一定是通过dp[1], dp[2] ,...., dp[n]得到的!

在第i时刻, 有两种情况(有任务和无任务)

这道题采用一种逆推的方法(即i 从 n 到 1枚举)

有任务时, 设k为该任务的时长, 我们需要枚举出该时刻开始的所有任务的时长k, 进行比较后选择能获得最大摸鱼时间的那个就完事了， 状态方程: dp[i] = max(dp[i], dp[i + k])

无任务时, 此时的空闲时间为上一刻的空闲时间+1 : dp[i] = dp[i + 1] + 1

你可能会想是一刻dp[i+1]是多少? 那不是另一个子问题吗? 然后计算机又笨笨地判断i+1有无任务，计算出最大空闲时间, 这样貌似构成了递归?(实际上动态规划是一种带着"记忆"的递归)

接下来写出代码应该问题不大: