从记忆化搜索到动态规划：状态表示、转移方程与空间优化

从记忆化搜索到动态规划

记忆化搜索

在搜索的过程中，如果搜索树中有很多重复的结点，此时可以通过一个'备忘录'，记录第一次搜索到的结果。当下一次搜索到这个结点时，直接在'备忘录'里面找结果。其中，搜索树中的一个一个结点，也称为一个一个状态。比如经典的斐波那契数列问题：

int f[N]; // 备忘录
int fib(int n) {
    // 搜索之前先往备忘录里面瞅瞅
    if (f[n] != -1)
        return f[n];
    if (n == 0 || n == 1)
        return f[n] = n;
    // 返回之前，把结果记录在备忘录中
    f[n] = fib(n - 1) + fib(n - 2);
    return f[n];
}

递归改递推

在用记忆化搜索解决斐波那契问题时，如果关注'备忘录'的填写过程，会发现它是从左往右依次填写的。当位置前面的格子填写完毕之后，就可以根据格子里面的值计算出位置的值。所以，整个递归过程，我们也可以改写成循环的形式，也就是递推：

int f[N]; // f[i] 表示：第 i 个斐波那契数
int fib(int n) {
    // 初始化前两个格子
    f[0] = 0; f[1] = 1;
    // 按照递推公式计算后面的值
    for (int i = 2; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    // 返回结果
    return f[n];
}

动态规划

动态规划（Dynamic Programming，简称 DP）是一种用于解决多阶段决策问题的算法思想。它通过将复杂问题分解为更小的子问题，并存储子问题的解（通常称为'状态'），从而避免重复计算，提高效率。因此，动态规划里，蕴含着分治与剪枝思想。