物理

浅析动态规划

动态规划，是信息学竞赛中的一种分治算法，也是最为基础的一种算法

简称DP

概念

动态规划，意在将一个完整的，大的问题，拆分成若干个小的，相似的流程

一般表现为“参数为xxx时的答案”

其中参数的数量不限

使用动态规划的要求：

1. 无后效性：不会干扰后面的决策（各决策彼此独立）
2. 可概括性：能够把问题分成相似若干小问题（问题本身的信息复杂度）
3. 传递性：存在一个固定的处理顺序可以利用前面求出的结果解决当前问题

一，数字金字塔（1998年国际信息学奥林匹克竞赛）

现给定一个n阶数字金字塔（第i行有i个点，每个点上有一个权值，共n行）

你可以从顶端出发，向左下方或右下方的点移动，走到底

求：你的路径上，各点权值之和的最大值

显然，直接暴力求解，需要$2^n$次计算

考虑将每一行分割开

对于一个点，你能在这里取得的最大权值=max（左上方点可取的最大权值，右上方点可取的最大权值）+该点权值

从上到下遍历，仅需$n^2$次运算

二，01背包（动态规划模板题）

题意：n个物品，m的空间，每个物品有价值w和体积v，求最大总价值

考虑用f[i][q]代表“有i个物品和q的空间”时的答案

显然，f[i][q]=max{f[i-1][q]，f[i][q-1]，f[i-1][q-v]+w}（此处v，w指第i个物品）

解决

以上两题是最为朴素，最好理解的动态规划，放在此处主要是为了供各位理解其思想

扩展延伸

动态规划并不只能用于线性的数据结构

能通过前面求出的各种状态的结果求出当前状态的答案的，都是动态规划

包括：树形DP，区间DP，状压DP，轮廓线DP等

挨个讲

树形DP

树形DP，顾名思义：在树状结构上进行动态规划的操作

可以与DFS结合使用

例题：树的最大独立集

题意：

每个节点有一权值w，选出若干点，令w之和最大，且点各不相邻，求此时“w之和”

解析：

令f[i][0]表示，以i为根的子树，在不选择i这个点时，最大的独立集权值和

令f[i][1]表示，以i为根的子树，在选择i这个点时，最大的独立集权值和

显然：

f[i][0]=∑ max（f[j][1]，f[j][0]）

f[i][1]=（∑ f[j][0]）+w

其中，j是i的子节点，w是i对应的权值

若一个节点是叶子节点，则可根据其对应的w求出该状态下的值

用DFS后根遍历整棵树，即可在根节点处得到答案

区间DP

这次，状态参数变成了区间的上界和下界

状态转移方式：

将当前状态分成两段求取结果，其中“分界点”需要枚举

记得初始化最底层答案

状压DP

全称“状态压缩动态规划”

将二维参数转化为一维参数枚举

适用于具体维数不知道的动态规划

轮廓线DP

以“插头”作为状态

基于连通性的状态压缩

常见于棋盘模型

经典问题“一条回路恰好经过每个格子”

“插头”表示路径方向（因为对于一个格子，一头进，一头出，只有两个“出入口”）

递推求出路径

若没有路径则无解

双重DP

这不是一个具体的算法，而是一个概念：

以一个DP算法作为状态转移解答另一个DP

先写这么多