动态规划基础¶

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

概念和思路¶

概念¶

把所求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解。

我们在问题（一个阶段）中用简单的信息描述一个局部的子问题，称为状态。

或者说，状态表示每个阶段开始面临的自然状况或客观条件。

问题的限制具有一定的局部性，于是我们可以用简单的转移将子问题连接起来。

通过这个过程，进而得到原问题的答案，称为转移（策略、决策）。

我们称，每个阶段的决策组成的序列称为策略，即求解问题的策略。

其中满足某些限制的称为允许策略集合，达到最优效果的策略称为最优策略。

动态规划就是这种，将问题分解为若干个相对简单的子问题的过程。

过程¶

动态规划所处理的问题是一个多阶段决策问题。

一般由边界状态开始，通过对中间阶段决策的选择，达到结束状态。

动态规划的关键就在于，找到合适的状态，通过合适的转移得到所有子问题的结果。

状态设计需要注意的点：在子问题中，当前记录的状态是不是足够处理问题的限制？

转移设计需要注意的点：是否不重不漏（计数）？是否找到了最优解（最优化）？

限制¶

最优化原理：问题的最优解所包括的子问题的解也是最优的。问题具有最优子结构，即满足最优化原理。即不管过去的过程如何，只从当前的状态和系统的最优化要求出发，作出下一步的最优决策。

无后效性：某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响曾经的状态，仅仅与当前状态有关。一个问题如果满足无后效性，那么大概率可以使用动态规划解决，我们按照一定的顺序求解，最终即可得到答案。

杂谈¶

往往可以通过增加状态的维数，记录更多的关键信息来满足无后效性与最优子结构。

但维数的增加会导致重叠子问题减少而影响时间效率，一般来说，

• 复杂度 \(=\) 状态数 \(\times\) 决策数目 \(\times\) 转移代价。

• 复杂度 \(=\) 实际状态数 \(+\) 总转移费用。

分类¶

按照状态分类¶

• 序列 DP
  • 线性 DP
  • 区间 DP
• 状压 DP
  • 子集 DP
  • 轮廓线 DP
  • 插头 DP
• 树形 DP
  • DAG DP
  • 换根 DP
  • 树形背包

按照目的分类¶

• 背包 DP
• 数学相关
  • 数位 DP
  • 计数 DP
  • 概率 DP
  • 期望 DP

一些优化方法¶

• 状态设计优化
• 数据结构优化
  • bitset 优化
  • 单调数据结构优化
  • 线段树优化
  • 平衡树优化
  • 动态 DP
• wqs 二分
• 矩阵乘法优化
• 四边形不等式、决策单调性、斜率优化

DFS、贪心、DP¶

关系¶

一般来说，从贪心，到 DP，到搜索，是判断某种条件越来越难。

因此，贪心解决的问题可以 DP 解决，DP 解决的问题可以搜索解决。

记忆化搜索¶

动态规划本身就是一种类似暴力的方法，但是对于大量重叠的子问题，动态规划会复用状态。

因此，如果我们在暴力搜索的时候加上复用状态，即记忆化搜索。

记忆化搜索一般可以优化到和动态规划一样的复杂度，但是由于递归本身常熟较大。

但是，如果如果很多状态是无用的、不会被转移到，那么记忆化搜索也会更快。

用记忆化搜索实现动态规划思路更加清晰，例如数位 DP 的时候就会大量使用记忆化搜索。

记忆化¶

使用 mem 数组表示记忆化的结果，我们一般初始化为 \(-1\) 表示未被搜索到。

function dfs(...)
    if mem[...] != -1:
        return mem[...]
    ans = ...
    return mem[...] = ans

有时一些状态不会被重复利用，那么可以将这些状态不记录，

function dfs(valid, ...)
    if valid and mem[...] != -1:
        return mem[...]
    ans = ...
    if valid:
        mem[...] = ans
    return ans

我们一般有两种方法来写记忆化搜索。

方法一¶

1. 写出状态转移方程；

2. 根据转移方程写出 DFS 函数；

3. 添加记忆化。

方法二¶

1. 写出暴搜 DFS 程序；

2. 修改为传入所有状态，与外部变量无关的递归；

3. 添加记忆化。

本页面最近更新：正在加载中，更新历史。
编辑页面：在 GitHub 上编辑此页！
本页面贡献者：RainPPR。