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

在递推形式的动态规划中，常用以下专有名词来表述：

• 状态表示：指 f 数组中每一个格子代表的含义。这个数组也被称为 dp 数组或 dp 表。
• 状态转移方程：指 f 数组中每一个格子是如何用其余的格子推导出来的。
• 初始化：在填表之前，根据题目中的默认条件或者问题的默认初始状态，将 f 数组中若干格子先填上值。

递推形式和递归形式是可以对应的：

• 状态表示 <—> 递归函数的意义（如求出第 n 个斐波那契数是多少）
• 状态转移方程 <—> 递归函数的主函数体
• 初始化 <—> 递归函数的递归出口

如何利用动态规划解决问题

第一种方式当然是记忆化搜索：

1. 先用递归的思想去解决问题；
2. 如果有重复子问题，就改成记忆化搜索的形式。

第二种方式，直接使用递推形式的动态规划解决：

1. 定义状态表示：一般情况下根据经验 + 递归函数的意义，赋予 dp 数组相应的含义。如果蒙的状态表示能解决问题，说明蒙对了；如果错了，再换一个试。
2. 推导状态转移方程：根据状态表示以及题意，在 dp 表中分析，当前格子如何通过其余格子推导出来。
3. 初始化：根据题意，先将显而易见的以及边界情况下的位置填上值。
4. 确定填表顺序：根据状态转移方程，确定按照什么顺序来填表。
5. 确定最终结果：根据题意，在表中找出最终结果。

下楼梯问题

题目描述

研究从楼梯顶跳到楼梯底有多少种方法。我们可以转换一下思路，研究从楼梯底跳到楼梯顶有多少种方法，这样正向思考更容易。

题目解析

1. 状态表示

猜测 f[i] 表示跳到第 i 个台阶有多少种方法，f[0] 表示地面。

2. 状态转移方程

推导状态转移方程的一般思路是根据最后一步划分情况。本题最后一步有三种情况：

• 从 i-1 跳一步走到 i
• 从 i-2 跳两步走到 i
• 从 i-3 跳三步走到 i

如果跳到 i-1 有 x 种情况，那么从 i-1 跳到 i 也有 x 种情况。同理，跳到 i-2 有 y 种，跳到 i-3 有 z 种。那么跳到 i 一共就有 x+y+z 种情况。

一句话总结：如果跳到 i-1 的情况确定了，跳到 i 的情况也就随之确定了。 所以本题的状态转移方程为：f[i] = f[i - 1] + f[i - 2] + f[i - 3]。

3. 初始化

初始化有两个意义：保证填表的正确性，以及保证填表的时候不越界。 对于本题来说，利用状态转移方程填前三个格子的时候就会发生数组越界访问，所以需要对前三个格子进行初始化。

• 下标 0 格子：把它初始化为 0 和 1 都解释得通，这种模棱两可的先不管，往后推几个格子再看。
• 下标 1 格子：只有一种情况。
• 下标 2 格子：有两种情况。
• 下标 3 格子：有四种情况。 为了满足状态转移方程，反推下标 0 格子应该填 1。然后就从下标 3 格子开始往后递推。

除了上面反推的方法，我们也可以完全忽略第一个格子，只初始化下标 1、下标 2、下标 3 这 3 个格子，从下标 4 开始往后递推。

4. 确定填表顺序

从左往右填表。

5. 最终结果

f[n] 即为结果。

注意：dp 数组中下标 0 表示地面，1 表示第一个台阶，依次类推。当题目 n 为 3 时表示一共有三个台阶，也就是需要拿到 dp[3] 的值，dp[3] 包括 dp[3] 本身一共会有 4 个格子，也就是说开辟的格子总数始终会比 n 多 1 个。

空间优化

原始版本在填表时，其实有很多空间是被浪费了的。比如在填下标 6 格子时，其实只用知道下标 3、4、5 的值就可以确定下标 6 格子的值，下标 0、1、2 的值是多余的。所以我们可以只开一个三个空间的小数组和一个临时变量 t 即可，小数组往后滚动即可完成递推，这种方法叫做滚动数组。

在此基础上再进一步优化，可以将三个空间的小数组优化为 3 个整型变量，也就是开四个整型变量 a, b, c, t 即可完成本题循环递推操作，它可以将 O(n) 的空间复杂度优化为 O(1)。

这里有两个注意事项：

1. 变量的赋值顺序需要严格按照从左往右：a = b, b = c, c = t。
2. 最后输出结果时需要判断台阶数 n 是否等于 1，如果等于 1 表示还没有进行循环赋值，直接输出 b，如果不等于 1 则输出 c。

代码实现

注意：本题 dp 数组元素范围可能超过 int 的最大值，所以 dp 数组的元素类型需要用 long long。

// 原始方法
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 70;
LL dp[N];

int main() {
    int n;
    cin >> n;
    // 初始化
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    // 根据状态转移方程递推填表
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    // 输出结果
    cout << dp[n] << endl;
    return 0;
}

// 利用滚动数组空间优化
#include <iostream>
using namespace std;
typedef long long LL;

int main() {
    int n;
    cin >> n;
    // 初始化
    LL a = 1, b = 1, c = 2, t = 0;
    // 往后滚动递推
    for (int i = 3; i <= n; i++) {
        t = a + b + c;
        a = b;
        b = c;
        c = t;
    }
    // 输出结果
    if (n == 1) cout << b << endl;
    else cout << c << endl;
    return 0;
}

数字三角形

题目描述

给定一个数字三角形，求从顶部到底部的路径最大权值和。

题目解析

首先分析本题如何存储原始数据，如果用链式树形结构存储比较麻烦，所以我们可以参考题目输入示例用一个二维数组存储。

接下来我们解决动态规划题目的标准流程：

1. 状态表示

开一个二维数组 dp，dp[i][j] 表示从 (1, 1) 走到 (i, j) 的所有方案中的最大权值。

2. 状态转移方程

推导状态转移方程需要根据最后一步划分情况。对于最后一个格子来说，最后一步可能来自两个格子的其中一个：一个是正上方，一个是左上方。 所以对于最后一个格子 i, j 来说，它的最大权值 dp[i][j] 就是取正上方 dp[i-1][j] 和左上方 dp[i-1][j-1] 格子权值的较大值，然后加上最后一个格子权值本身 a[i][j]。 状态转移方程就是： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]

3. 初始化

因为本题计算格子最大权值需要拿格子正上方和左上方的格子最大权值，所以就会越界访问到非正常填表区域的格子（最上面一行和最左边一列）。 但是对于本题来说，因为我们只会填正方形给的左下半部分，所以只会越界访问到左边绿色一列。 解决方法就是在填表时访问到这些区域时'装作没看到'，就是在 max 二取一时只会取有效格子的值。因为 max 是取较大值，并且本题的输入范围是 [0, 100]，所以只要将这些越界区域初始化为 0 就可以保证只会取到有效格子的值了。

4. 填表顺序

填表顺序仅需保证从上往下填即可，填同一行时无需关注左右顺序，因为填表时我们只关心上一行的值。

5. 最终结果

dp 数组最后一行的最大值。

空间优化

这里我们也可以对二维数组进行空间优化，将 O(N^2) 的空间复杂度优化为 O(N)。 具体操作如下：对于本题来说，填格子是按行来填的，并且因为本题填格子时只关注正上方和左上方的格子，所以填一行格子时只关注上一行的格子情况。比如填第四行时只要有第三行的格子数据就足够了，第一行和第二行的格子是多余的。 所以我们可以只开一个一维数组 f，用数组 f 进行填表。更新公式为： f[j] = max(f[j], f[j - 1]) + a[i][j]

空间优化都需要注意填表顺序。本题更新一个位置格子数据时需要访问该位置原本的数据和该位置左边格子原本的数据，所以在更新一个位置格子数据时它左边的格子不能比它先更新，所以我们需要按照从右往左的顺序更新格子数据。 体现在代码中我们只用修改两个地方：

1. 将二维 dp 数组改为一维，把二维数组的第一维删掉。
2. 修改每行格子的更新顺序。

总结：对于二维转一维的空间优化我们只用关注两个地方，第一判断是否需要修改遍历更新顺序，第二在代码中只用将二维数组第一维删掉即可。

代码实现

// 原始方法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N], dp[N][N];

int main() {
    int r;
    cin >> r;
    // 处理输入
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    // 初始化，全局开辟的数组数据天然为 0
    // 按序填表
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
        }
    }
    // 输出结果
    int ret = 0;
    for (int i = 1; i <= r; i++) {
        ret = max(ret, dp[r][i]);
    }
    cout << ret << endl;
    return 0;
}

// 空间优化后代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int a[N][N], dp[N];

int main() {
    int r;
    cin >> r;
    // 处理输入
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
        }
    }
    // 初始化，全局开辟的数组数据天然为 0
    // 按序填表
    for (int i = 1; i <= r; i++) {
        for (int j = i; j >= 1; j--) {
            dp[j] = max(dp[j], dp[j - 1]) + a[i][j];
        }
    }
    // 输出结果
    int ret = 0;
    for (int i = 1; i <= r; i++) {
        ret = max(ret, dp[i]);
    }
    cout << ret << endl;
    return 0;
}