目录

• 动态规划基础及线性动态规划
  • 动态规划的状态及记忆化搜索
    • 状态
      • 状态的特点
      • 状态的转移
    • 实现
    • 记忆化搜索
      • 例题：摆花
      • 例题：滑雪
      • 小结
  • 线性动态规划
    • 例题：假期
    • 例题：小奇挖矿
    • 例题：大搬家
    • 例题：说真话

动态规划基础及线性动态规划

动态规划的状态及记忆化搜索

动态规划\((Dynamic Programming，DP)\)就是通过对问题的拆分，

定义问题的状态和状态之间的关系。

使得问题能够通过递推（或是分治）的方式去解决。

状态

状态的本质是某个问题的子问题。

和搜索算法类似，只有当确定状态后，才能找到状态之间的联系。

由于问题形式不一，所以状态也各种各样，

对于问题要具体分析，才能找到合适的状态。

一般情况下，可以通过所求的东西和一些影响结果的量来确定状态。

状态的特点

• 无后效性

  某阶段的状态一旦确定，

  则此后过程的演变 不再受此前各种状态及决策的影响。

  简单的说，就是 “未来与过去无关”，

  当前的状态是此前历史的一个完整总结，

  此前的历史只能通过当前的状态去影响过程未来的演变。

• 最优子结构

  子问题的局部最优将导致整个问题的全局最优，

  即问题具有最优子结构的性质，

  也就是说一个问题的最优解只取决于其子问题的最优解，

  非最优解对问题的求解没有影响。

状态的转移

状态的转移即为状态之间的联系。

通过状态之间的的联系，能够对问题进行求解。

一般来说，状态转移方程可以写成一个递推式的形式。

对于同一问题的不同状态定义来说，状态的转移也可能是不同的。

实现

动态规划的实现就是自底向上枚举每一种状态，

之后通过状态转移方程进行求解。

由于一种状态至多会被计算一次，

所以动态规划的复杂度一般与状态数有关，为多项式级别。

记忆化搜索

记忆化搜索 属于 搜索的一种剪枝方式，

即通过递归的方法对状态进行求解。

在一般情况下，记忆化搜索仍采用自顶向下的顺序，

但每当求解出一个状态，就将它的解保存下来。

当以后再次遇见就这个状态的时候，便不需要重新求解。

与动态规划相同，每种状态只会被计算一次，复杂度一般也被多项式级别。

在某些情况下，动态规划可以与记忆化搜索相互替代。

例题：摆花

有 \(n\) 种花，按照顺序排成一排 \(m\) 朵，

第 \(i\) 种花最多可以 放 \(a_i\) 个，最少放\(1\)个。

要求所有花必须按照种类递增摆放，且同种花完全一样.

现在问有多少种不同的摆放方案。

数据范围 \(n, m \leq 200\)

题解：可以用动态规划或者记忆化搜索解决。

状态为 \(f[i][j]\) 表示只考虑前 \(i\) 种花，一共摆放了 \(j\) 朵的方案数。

转移只要枚举当前这种花放了几盆即可。

\[f[i][j]=f[i-1][j-k](1\leq k\leq a_i) \]

例题：滑雪

滑雪场是一个 \(n * m\) 的网格图，其中每个点的权值代表该点的高度。

滑雪的时候只能从相邻两格中较高的那格滑到较低的那格。

现在问这个滑雪场中最长可以滑行的距离。

数据范围 \(n, m \leq 1000\)

题解：定义状态 \(f[x][y]\) 表示从点 \((x, y)\) 开始所能走的最长路。

如果我们要用动态规划解决这个问题，需要先将所有点按照高度排序。

但如果我们用记忆化搜索则不需要。

小结

• 记忆化搜索相比动态规划更好理解，代码实现更为容易。
• 对于一些状态顺序不明确的题目，用记忆化搜索更为方 便。
• 记忆化搜索可以剪去一些无效状态。
• 记忆化搜索由于使用递归，常数较大。
• 记忆化搜索优化起来相较动态规划更加困难。

线性动态规划

在所有动态规划中，线性动态规划最常见，最基础， 也最重要。

学好线性动态规划有助于我们更快更好地设计状态与转 移方程，

并对动态规划有更深的理解。

例题：假期

小 \(L\) 的暑假有 \(n\) 天，他想要在暑假过的充实。

每一天，小 \(L\) 可以选择去游泳、学编程或在家休息。

小 \(L\) 不想连续两天参加相同的活动（休息不算活动）。

现在给出 \(n\) 天中游泳池和机房的开放情况，

问小 \(L\) 在 \(n\) 天中最少休息几天。

数据范围 \(n \leq 10^5\)

题解：容易想到可以用每天做的事情以及天数来表示状态

\(f[i]\)表示第 \(i\) 天在家休息前 \(i\) 天最少休息几天。

\(g[i]\) 表示第 \(i\) 天去游泳前 \(i\) 天最少休息几天。

\(h[i]\) 表示第 \(i\) 天去编程前 \(i\) 天最少休息几天。

\(f[i] = min(f[i?1], g[i?1], h[i?1]) + 1\)

\(g[i] = min(f[i?1], h[i?1])\) （如果第 \(i\) 天游泳池开放）

\(h[i] = min(f[i?1], g[i?1])\) （如果第 \(i\) 天机房开放）

时间复杂度 \(O(n)\)，空间复杂度 \(O(n).\)

例题：小奇挖矿

现在有 \(m + 1\) 个星球，从左到右标号为 \(0\) 到 \(m\)，小奇最初在 \(0\) 号星球。

有 \(n\) 处矿体，第 \(i\) 处矿体有 \(a_i\) 单位原矿，在第 \(b_i\) 个星球上。

由于飞船使用的是老式的跳跃引擎，

每次它只能从第 \(x\) 号星球移动到第 \(x + 4\) 号星球或 \(x + 7\) 号星球。

每到一个星球，小奇会采走该星球上所有的原矿，

求小奇能采到的最大原矿数量。

注意，小奇不必最终到达 \(m\) 号星球。

数据范围 \(n \leq 10^5, m \leq 10^9.\)

题解：一个最直接的想法是用 \(f[i]\) 表示走到第 \(i\) 个星球最多可以收集多少矿物。

但是由于 \(m\) 非常大，而这个算法复杂度是 \(O(m)\)，所以不可行。

发现如果相邻两处矿脉相差 \(> 17\)，那么他们之间一定能互相到达。

所以可以将所有相邻距离 \(> 17\) 的矿脉之间的距离都改为 \(18\)。

那么可以将 \(m\) 缩小到 \(18*n\) 的范围内，即可用 \(O(m)\) 的算法 通过。

时间复杂度 \(O(n*18)\)，空间复杂度 \(O(n*18).\)

例题：大搬家

现在有一个长度为 \(n\) 的搬家指示，

其中 \(a_i\) 表示住在第 \(i\) 栋房子的人需要搬家到第 \(a_i\) 栋房子里。

由于政府一时脑抽，这 \(n\) 户人家连续进行了三次搬家，

大家发现一次搬家后的结果正好和三次搬家的结果一样。

问有多少种不同的数列 \(a_i\)，答案对 \(1000000007\) 取模。

数据范围 \(n \leq 10^6.\)

题解：由于进行两次搬家后结果不变，所以 \(a\) 这个置换只包含一元环与二元环。

考虑 \(f[i]\) 表示长度为 \(i\) 的数列 \(a\) 的方案数。之后分两种情况进行转移。

• 新加入的 \(a_i = i\)，那么从 \(f[i?1]\) 转移过来。

• 新加入的 \(a_i = j\)，那么有 \(a_j = i\)，其 中 \(i,j\) 都为新加入的，

  所以从 \(f[i?2]\) 转移过来。

综上有 \(f[i] = f[i?1] + f[i?2] * (i ? 1)\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n).\)

例题：说真话

一次考试共有 \(n\) 个人参加，

第 \(i\) 个人说：“有 \(a_i\) 个人分数 比我高，\(b_i\)个人分数比我低。”

问最少有几个人没有说真话(可能有相同的分数)

数据范围 \(n \leq 100000\)

题解：最少多少人说假话话 等价于 \(n-\)最多多少人说真话。

我们发现，对于第 \(i\) 个人，如果有 \(a_i\) 个分数比他高，有 \(b_i\)个分数比他低，

那么说明区间 \([a_i + 1, n ? b_i ]\)中所有人的分数相同。

所以我们可以将每个人表示成一个区间 \([l_i ,r_i ]\)。

如果两个人所在的区间相交却不重合，那么他们一定不 能同时合法。

如果有超过 \((r_i ? l_i + 1)\) 个人的区间同时为 \([l_i ,r_i ]\)，

那么最多只能有 \((r_i ? l_i + 1)\) 个人合法。

所以我们可以统计出每一种区间出现的次数，并按 照 \(r_i\) 顺序排序。

用 \(s_i\) 表示区间 \([l_i ,r_i ]\) 中有多少人合法。

定义状态 \(f_i\) 表示前 \(i\) 名最多有多少人合法。

之后考虑从前向后枚举每一种区间。

容易得到转移 \(f[r_i] = max(max(f[1], ..., f[l_i?1]) + s_i , f[r_i] )\)。

使用前缀最大值即可解决问题。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n).\)