动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。
动态规划需要满足以下三种性质：
- 最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 子问题重叠性质：子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
- 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
线性DP
介绍尚待完善
LCS
LIS
P2501 [HAOI2006]数字序列
第一问应该还是比较简单的，发现严格单增不太好处理，我们一般都可以使 \(b[i]=a[i]-i\)，这样就只要在 \(b\) 上求单调不降就行了，有两种做法，一种是树状数组，一种是二分。
第二问：在 \(b\) 上修改使得 \(b\) 单调不降，考虑如何使代价最小。
设 \(ans_i\) 表示 \(1\sim i\) 的答案，
\(w(j,i)\) 表示将 \([j,i]\) 标为合法的最小变化幅度。
因为 \(f_i=f_j+1\), 所以\(\forall j < k <i\), 要么 \(b_k \le b_j\)，要么 \(b_i \le b_k\)，现在有一个结论是，\(w(j,i)\) 的方案，一定会以一个分界点 \(k\) 使得 \([j,k]\) 均为 \(b_j\)，\([k+1,i]\) 均为 \(b_i\)
试着浅浅证明一下。
设 \(j<k<i\) ，修改后的数字为 \(c_k\) 显然 \(b_i\le c_k \le b_i\)
上图给出了一种修改方案，图可能画的有点草率，请见谅，考虑是否能更改使得答案更优。
对于一段连续修改为 \(c\) 的一段区间 \([l,r]\):
1.若 \(b_k < b_j\) 的数量大于 \(b_k > b_j\)，则显然 \(c\) 越小 ,代价越小，则 \(c=c_{l-1}\)时最优。
2.如果相反，则 \(c=c_{r+1}\) 时最优。
3.若数量相等，则任意 \(c\) 都行。
则有如下修改过程。
发现满足结论。
所以 \(i\), 枚举 \(j\) 使得 \(f_j + 1 = f_i\) ，再枚举 \(k\), 求得最小代价，
显然可以用前缀和优化，复杂度 \(O(n^2)\)，\([j,i]\) 的长度较小，可以跑过去。
循环到 n + 1 的目的： 因为不保证 \(b_n\) 一定在最长不降序列上，所以要手动加一个无穷大来使得\(b_{n+1}\) 成为最后一个元素。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 51;
inline int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
int n, len;
int a[N], b[N], f[N], g[N];
ll ans[N], pre[N], suf[N];
vector<int> ed[N];
int main(){
n = read();
for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i] - i;
b[0] = -1e9, b[n + 1] = 1e9;
for(int i = 1; i <= n + 1; ++i){
int l = 0, r = len, x = 0;
while(l <= r){
int mid = (l + r) >> 1;
if(g[mid] <= b[i]) x = mid, l = mid + 1;
else r = mid - 1;
}
len += (x == len), f[i] = x + 1, g[x + 1] = b[i], ed[f[i]].push_back(i); //b 的最长不降子序列可能有多个
}
printf("%d\n", n - len + 1);
memset(ans, 0x3f, sizeof(ans)); ans[0] = 0;
ed[0].push_back(0);
for(int i = 1; i <= n + 1; ++i){
for(auto j : ed[f[i] - 1]){
if(j > i || b[j] > b[i]) continue; //合法性判断
pre[j] = suf[i] = 0;
for(int k = j + 1; k < i; ++k) pre[k] = pre[k - 1] + abs(b[j] - b[k]);
for(int k = i - 1; k > j; --k) suf[k] = suf[k + 1] + abs(b[i] - b[k]);
for(int k = j; k < i; ++k) ans[i] = min(ans[i], ans[j] + pre[k] + suf[k + 1]);
}
}
printf("%lld\n", ans[n + 1]);
return 0;
}
P3336 [ZJOI2013]话旧
因为极小值均为 \(0\)：极小值也就是函数导函数为0时的值，也就是说如果路径要下降就要下降到 \(0\)。
设 \(f[i][0/1]\) 表示到\(i\)的路径是往上还是往下的，考虑转移（i时给定 k 的那些点）。
-
\(f[i][1]\rightarrow f[i+1][0]\)
先考虑最简单的一种情况，即当前点的路径还在往下，而要用一条往上的路径穿过 \(i+1\)。那么延长这两条路径，能够确定两个 \(0\) 点，剩下的就是在这两个零点之间反复横跳，设这两个零点之间的距离为 \(2l\)，那么要进行 \(l\) 次向上 \(l\) 次向下，而分组后两者的分组必定两两相等，所以就是把 \(l\) 分成任意数量组的方案数，这个答案是 \(2^{k-1}\)。k−1。即对于\(j\)考虑，其要么和\(j-1\)在一组要么不在。
-
\(f[i][1]\rightarrow f[i+1][1]\)
首先 \(i\)这个点一定要走到 \(0\), \(i + 1\) 也是类似，所以同上确定两个 \(0\) 点。因为 \(i + 1\) 要从上面下来，所以平移一下就好了，可以看图。
-
\(f[i][0] \rightarrow f[i+1][0]\)
强行把\(i\)当做当前\(i\)节点的往上的路径的终点，那么又能确定两个\(0\)点，还是假设中间有\(2k\)个位置，这时候的答案是\(2^k\)。首先还是可以任意分组，但是第一次还可以选择是否从\(i\)继续向上延伸。
-
\(f[i][0]\rightarrow f[i+1][1]\)
还是强制到 \(0\)，那么同上此时的贡献为 \(2^k\)
那么直接dp就完了，最大值显然易得。
一些 \(k\) 等于 \(0\) 的情况直接特判就行了。