动态规划 Dynamic Programming

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

  1. 要去刻画最优解的结构特征;
  2. 尝试递归地定义最优解的值(就是我们常说的考虑从 i1i-1 转移到 ii);
  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));
  // ...
}