动态规划 Dynamic Programming

动态规划应用于子问题重叠的情况：

1. 要去刻画最优解的结构特征；
2. 尝试递归地定义最优解的值（就是我们常说的考虑从 $i-1$ 转移到 $i$）；
3. 计算最优解；
4. 利用计算出的信息构造一个最优解。

记忆化搜索 Memoization

记忆化搜索是个很重要的优化方法，是指将计算较昂贵的函数调用的结果缓存下来，然后在后续调用时直接使用。记忆化搜索是实现DP的时候，经常使用的优化。

int g[MAXN];
 
int f(状态参数) {
  if (g[规模] != 无效数值) return g[规模];
  if (终止条件) return 最小子问题解;
  g[规模] = f(缩小规模);
  return g[规模];
}
 
int main() {
  // ...
  memset(g, 无效数值, sizeof(g));
  // ...
}