引入:[IOI1994] 数字三角形}
给定一个 \(r\) 行的数字三角形（ \(r \leq 1000\) ），需要找到一条从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到当前点左下方的点或右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 \(7 \to 3 \to 8 \to 7 \to 5\) 的路径产生了最大数字和.
最简单粗暴的思路是尝试所有的路径。因为路径条数是 \(O(2^r)\) 级别的，这样的做法无法接受。
注意到这样一个事实，一条最优的路径，它的每一步决策都是最优的。
以例题里提到的最优路径为例，只考虑前四步 \(7 \to 3 \to 8 \to 7\)，不存在一条从最顶端到 \(4\) 行第 \(2\) 个数的权值更大的路径。
而对于每一个点，它的下一步决策只有两种：往左下角或者往右下角（如果存在）。因此只需要记录当前点的最大权值，用这个最大权值执行下一步决策，来更新后续点的最大权值。
这样做还有一个好处：我们成功缩小了问题的规模，将一个问题分成了多个规模更小的问题。要想得到从顶端到第 \(r\) 行的最优方案，只需要知道从顶端到第 \(r-1\) 行的最优方案的信息就可以了。
这时候还存在一个问题：子问题间重叠的部分会有很多，同一个子问题可能会被重复访问多次，效率还是不高。解决这个问题的方法是把每个子问题的解存储下来，通过记忆化的方式限制访问顺序，确保每个子问题只被访问一次。
上面就是动态规划的一些基本思路。下面将会介绍动态规划的思想。
动态规划原理
能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。
给定一个长度为 \(n\) 的序列 \(A\) 和一个 长度为 \(m\) 的序列 \(B\) （ \(n,m \leq 5000\) ），求出一个最长的序列，使得该序列既是 \(A\) 的子序列,也是 \(B\) 的子序列
前提：字符串 \(S\) 的 子序列 是从 \(S\) 中将若干元素提取出来并不改变相对位置形成的序列，即 \(S[p_1],S[p_2],\ldots,S[p_k]\) ， \(1\le p_1< p_2<\cdots< p_k\le|S|\) 。
设 \(f(i,j)\) 表示只考虑 \(A\) 的前 \(i\) 个元素， \(B\) 的前 \(j\) 个元素时的最长公共子序列的长度，求这时的最长公共子序列的长度就是 子问题。 \(f(i,j)\) 就是我们所说的 状态，则 \(f(n,m)\) 是最终要达到的状态，即为所求结果。
对于每个 \(f(i,j)\) ，存在三种决策：如果 \(A_i=B_j\) ，则可以将它接到公共子序列的末尾；另外两种决策分别是跳过 \(A_i\) 或者 \(B_j\)。状态转移方程如下：
该做法的时间复杂度为 \(O(nm)\) 。
另外，本题存在
\(O\left(\dfrac{nm}{w}\right)\) 的算法。有兴趣的读者可以自行探索。
最长不下降子序列
给定一个长度为 \(n\) 的序列 \(A\)（ \(n \leq 5000\) ），求出一个最长的 \(A\) 的子序列，满足该子序列的后一个元素不小于前一个元素。
设 \(f(i)\) 表示以 \(A_i\) 为结尾的最长不下降子序列的长度，则所求为 \(\max_{1 \leq i \leq n} f(i)\) 。
计算 \(f(i)\) 时，尝试将\(A_i\) 接到其他的最长不下降子序列后面，以更新答案。于是可以写出这样的状态转移方程： $$ f(i)=\max_{1 \leq j < i, A_j \leq A_i} (f(j)+1) $$ 。
容易发现该算法的时间复杂度为 \(O(n^2)\) 。
int a[MAXN], d[MAXN];
int dp() {
d[1] = 1;
int ans = 1;
for (int i = 2; i <= n; i++) {
d[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] <= a[i]) {
d[i] = max(d[i], d[j] + 1);
ans = max(ans, d[i]);
}
}
return ans;
}