动态规划算法解决货物堆放问题：记忆化搜索和拓扑排序C++实现

一、动态规划算法解决货物堆放问题：记忆化搜索算法

1. 算法概念

原理

本算法使用动态规划（记忆化搜索）解决货物堆放问题。将问题抽象为在有向无环图（DAG）中寻找最长路径的问题：

• 每个货物表示图中的一个节点
• 如果货物A可以放在货物B下面，则存在一条从B到A的有向边
• 目标是找到最长的路径，即最大堆放高度

数学基础

定义状态：

• h[v]：以货物v为顶部时的最大堆放高度

状态转移方程：

h[v] = 1 + max(h[u])，其中u是v可以放置的所有货物

如果v下面不能放置任何货物，则h[v] = 1

时间复杂度

• 每个节点只计算一次：O(n)
• 每个边只遍历一次：O(m)
• 总时间复杂度：O(n + m)，其中n是货物数量，m是依赖关系数量

空间复杂度

• 邻接表存储图：O(n + m)
• 记忆化数组：O(n)
• 总空间复杂度：O(n + m)

2. 示意图

有向无环图

货物堆放图

算法流程图

3. 算法优势分析

该算法通过记忆化搜索实现了动态规划，避免了重复计算：

这种方法特别适合解决有向无环图的最长路径问题，时间复杂度低且实现简洁。

4. C++代码实现

#include <iostream>
#include <vector>
#include <iomanip> // 用于格式化输出

using namespace std;

// 计算以货物v为顶部时的最大堆放高度
// v: 当前货物编号
// pre: 邻接表，pre[v]表示可以放在v下面的货物列表
// h: 记忆化数组，h[v]表示以v为顶部时的最大高度，0表示未计算
int max_height(int v, vector<vector<int>>& pre, vector<int>& h) {
// 如果已经计算过，直接返回记忆结果
if (h[v] != 0) return h[v];

// 初始化当前货物的最大高度为0
h[v] = 0;

// 遍历所有可以放在v下面的货物
for (auto u : pre[v]) {
// 递归计算以u为顶部的最大高度，并取最大值
h[v] = max(h[v], max_height(u, pre, h));
}

// 加上当前货物自身的高度（1个货物高度单位）
h[v]++;

return h[v];
}

int main() {
cout << "========== 动态规划解决货物堆放问题 ==========" << endl << endl;

// 测试用例1: 有向无环图
{
cout << "【测试用例1】" << endl;
int n = 5; // 货物个数
vector<vector<int>> pre(n); // 邻接表，pre[i]包含所有可以放在货物i下面的货物编号
vector<int> h(n, 0); // 货物i在最上方时的最大堆放高度记忆化数组，初始为0表示未计算

// 建立依赖关系：如果u可以放在v下面，则pre[v]包含u
pre[2].push_back(1); // 货物1可以放在货物2下面
pre[1].push_back(4); // 货物4可以放在货物1下面
pre[3].push_back(4); // 货物4可以放在货物3下面
pre[0].push_back(2); // 货物2可以放在货物0下面
pre[2].push_back(4); // 货物4可以放在货物2下面
pre[0].push_back(3); // 货物3可以放在货物0下面

// 打印依赖关系表
cout << "货物依赖关系表：" << endl;
cout << "+———+———————–+" << endl;
cout << "| 货物编号 | 可放在下面的货物编号 |" << endl;
cout << "+———+———————–+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | ";
if (pre[i].empty()) {
cout << " 无 ";
}
else {
for (int j = 0; j < pre[i].size(); j++) {
cout << pre[i][j];
if (j < pre[i].size() – 1) cout << ", ";
}
// 补齐空格
for (int k = 0; k < 15 – 2 * pre[i].size(); k++) {
cout << " ";
}
}
cout << "|" << endl;
}
cout << "+———+———————–+" << endl << endl;

// 打印计算过程
cout << "动态规划计算过程：" << endl;
cout << "+———+———————+———————+" << endl;
cout << "| 货物编号 | 依赖的货物计算结果 | 当前货物最大高度 |" << endl;
cout << "+———+———————+———————+" << endl;

int ans = 0;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | ";

// 先打印依赖的货物计算结果
if (pre[i].empty()) {
cout << " 无 ";
}
else {
for (int j = 0; j < pre[i].size(); j++) {
cout << "h[" << pre[i][j] << "]=";
// 如果依赖的货物还未计算，先计算
if (h[pre[i][j]] == 0) {
int temp_h = h[pre[i][j]]; // 保存当前值
// 这里不实际调用，只是显示
cout << "?";
if (j < pre[i].size() – 1) cout << ", ";
}
else {
cout << h[pre[i][j]];
if (j < pre[i].size() – 1) cout << ", ";
}
}
// 补齐空格
int spaces = 20 – 7 * pre[i].size();
for (int k = 0; k < spaces; k++) cout << " ";
}

// 计算当前货物的最大高度
int current_max = 0;
for (auto u : pre[i]) {
current_max = max(current_max, max_height(u, pre, h));
}
h[i] = current_max + 1;

cout << "| " << h[i] << " |" << endl;
ans = max(ans, h[i]);
}
cout << "+———+———————+———————+" << endl;

cout << "测试用例1: n=5, 6个关系对" << endl;
cout << "最大堆放高度: " << ans << endl << endl;

// 打印最终结果
cout << "最终结果：" << endl;
cout << "+———+———————+" << endl;
cout << "| 货物编号 | 作为顶部的最大高度 |" << endl;
cout << "+———+———————+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | " << h[i] << " |" << endl;
}
cout << "+———+———————+" << endl;
cout << "| 最大值 | " << ans << " |" << endl;
cout << "+———+———————+" << endl << endl;
}

cout << "==========================================" << endl << endl;

// 测试用例2: 简单链式结构
{
cout << "【测试用例2】" << endl;
int n = 4;
vector<vector<int>> pre(n);
vector<int> h(n, 0);

pre[0].push_back(1);
pre[1].push_back(2);
pre[2].push_back(3);

int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, max_height(i, pre, h));
}

cout << "测试用例2: n=4, 3个关系对" << endl;
cout << "最终高度表：" << endl;
cout << "+———+———————+" << endl;
cout << "| 货物编号 | 作为顶部的最大高度 |" << endl;
cout << "+———+———————+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | " << h[i] << " |" << endl;
}
cout << "+———+———————+" << endl;
cout << "最大堆放高度: " << ans << endl << endl;
}

cout << "==========================================" << endl << endl;

// 测试用例3: 单个货物
{
cout << "【测试用例3】" << endl;
int n = 1;
vector<vector<int>> pre(n);
vector<int> h(n, 0);

int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, max_height(i, pre, h));
}

cout << "测试用例3: n=1, 没有关系依赖" << endl;
cout << "最终高度表：" << endl;
cout << "+———+———————+" << endl;
cout << "| 货物编号 | 作为顶部的最大高度 |" << endl;
cout << "+———+———————+" << endl;
cout << "| 0 | " << h[0] << " |" << endl;
cout << "+———+———————+" << endl;
cout << "最大堆放高度: " << ans << endl << endl;
}

return 0;
}

5. 输出结果

========== 动态规划解决货物堆放问题 ==========

【测试用例1】
货物依赖关系表：
+———+———————–+
| 货物编号 | 可放在下面的货物编号 |
+———+———————–+
| 0 | 2, 3 |
| 1 | 4 |
| 2 | 1, 4 |
| 3 | 4 |
| 4 | 无 |
+———+———————–+

动态规划计算过程：
+———+———————+———————+
| 货物编号 | 依赖的货物计算结果 | 当前货物最大高度 |
+———+———————+———————+
| 0 | h[2]=?, h[3]=? | 4 |
| 1 | h[4]=1 | 2 |
| 2 | h[1]=2, h[4]=1 | 3 |
| 3 | h[4]=1 | 2 |
| 4 | 无 | 1 |
+———+———————+———————+
测试用例1: n=5, 6个关系对
最大堆放高度: 4

最终结果：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 4 |
| 1 | 2 |
| 2 | 3 |
| 3 | 2 |
| 4 | 1 |
+———+———————+
| 最大值 | 4 |
+———+———————+

==========================================

【测试用例2】
测试用例2: n=4, 3个关系对
最终高度表：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 4 |
| 1 | 3 |
| 2 | 2 |
| 3 | 1 |
+———+———————+
最大堆放高度: 4

==========================================

【测试用例3】
测试用例3: n=1, 没有关系依赖
最终高度表：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 1 |
+———+———————+
最大堆放高度: 1

二、动态规划算法解决货物堆放问题：拓扑排序算法

1. 算法概念

原理

本算法使用拓扑排序结合动态规划解决货物堆放问题。拓扑排序确保按照依赖关系的顺序处理货物，这样当处理一个货物时，它所依赖的所有货物都已经处理完毕。

算法步骤

数学基础

定义：

• 图 G = (V, E)，其中 V 是货物集合，E 是依赖关系
• 对于边 (u, v) ∈ E，表示 u 可以放在 v 下面

状态转移方程：

h[v] = 1 + max{h[u] | (u, v) ∈ E}

如果v下面不能放置任何货物，则 h[v] = 1

时间复杂度

总时间复杂度：O(n + m)，其中n是货物数量，m是依赖关系数量

空间复杂度

总空间复杂度：O(n + m)

2. 算法流程图

3. 算法优势分析

4. C++代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip> // 用于格式化输出

using namespace std;

// 拓扑排序函数
// 参数：
// n: 货物数量
// nex: 邻接表，nex[u]存储可以放在u上面的货物列表（即u→v的有向边）
// 返回值：拓扑排序序列
vector<int> TopologicalSort(int n, const vector<vector<int>>& nex) {
vector<int> in_deg(n, 0); // 每个节点的入度数组，初始化为0

// 计算每个节点的入度
for (int u = 0; u < n; u++) {
for (auto v : nex[u]) {
in_deg[v]++; // u指向v，所以v的入度加1
}
}

// 创建队列，将所有入度为0的节点加入队列
queue<int> q;
for (int u = 0; u < n; u++) {
if (in_deg[u] == 0) {
q.push(u);
}
}

// 拓扑排序结果序列
vector<int> permutation;

// 打印入度表
cout << "拓扑排序入度表：" << endl;
cout << "+———+———+" << endl;
cout << "| 货物编号 | 初始入度 |" << endl;
cout << "+———+———+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | " << in_deg[i] << " |" << endl;
}
cout << "+———+———+" << endl << endl;

// 开始拓扑排序
int step = 0;
cout << "拓扑排序过程：" << endl;
cout << "+——-+——————-+——————-+" << endl;
cout << "| 步骤 | 队列中的货物 | 拓扑排序序列 |" << endl;
cout << "+——-+——————-+——————-+" << endl;

// 初始队列状态（第0步）
cout << "| 0 | ";
queue<int> init_q = q;
vector<int> init_items;
while (!init_q.empty()) {
init_items.push_back(init_q.front());
init_q.pop();
}
if (init_items.empty()) {
cout << " 空 ";
}
else {
for (size_t i = 0; i < init_items.size(); i++) {
cout << init_items[i];
if (i < init_items.size() – 1) cout << ", ";
}
int spaces = 17 – 3 * init_items.size();
for (int i = 0; i < spaces; i++) cout << " ";
}
cout << "| 空 |" << endl;

while (!q.empty()) {
step++;
int u = q.front(); // 取出队首节点
q.pop();
permutation.push_back(u); // 加入拓扑序列

// 处理u的所有后继节点
for (auto v : nex[u]) {
in_deg[v]–;
if (in_deg[v] == 0) {
q.push(v);
}
}

// 打印当前状态（处理完后继节点后）
cout << "| " << step << " | ";

// 重新获取当前队列内容用于显示
queue<int> q_copy = q;
vector<int> queue_items;
while (!q_copy.empty()) {
queue_items.push_back(q_copy.front());
q_copy.pop();
}

// 打印队列内容
if (queue_items.empty()) {
cout << " 空 ";
}
else {
for (size_t i = 0; i < queue_items.size(); i++) {
cout << queue_items[i];
if (i < queue_items.size() – 1) cout << ", ";
}
// 补齐空格
int spaces = 17 – 3 * queue_items.size();
for (int i = 0; i < spaces; i++) cout << " ";
}

cout << "| ";

// 打印当前拓扑序列
for (size_t i = 0; i < permutation.size(); i++) {
cout << permutation[i];
if (i < permutation.size() – 1) cout << " → ";
}
// 补齐空格
int spaces = 17 – 3 * permutation.size();
for (int i = 0; i < spaces; i++) cout << " ";
cout << "|" << endl;
}

cout << "+——-+——————-+——————-+" << endl << endl;
return permutation;
}

// 计算最大堆放高度
// 参数：
// permutation: 拓扑排序序列
// pre: 邻接表，pre[v]存储可以放在v下面的货物列表
// 返回值：最大堆放高度
int calculate_max_height(const vector<int>& permutation, const vector<vector<int>>& pre) {
int n = permutation.size();
int ans = 0; // 最大高度
vector<int> h(n, 0); // h[v]表示以货物v为顶部时的最大高度

cout << "动态规划计算过程：" << endl;
cout << "+——-+———+——————-+——————-+" << endl;
cout << "| 步骤 | 货物编号 | 依赖货物最大高度 | 当前货物最大高度 |" << endl;
cout << "+——-+———+——————-+——————-+" << endl;

// 按拓扑顺序处理每个节点
for (size_t idx = 0; idx < permutation.size(); idx++) {
int v = permutation[idx]; // 当前货物

// 计算h[v] = 1 + max(h[u])，其中u是v可以放置的所有货物
for (auto u : pre[v]) {
h[v] = max(h[v], h[u]);
}

// 加上当前货物自身
ans = max(ans, ++h[v]);

// 打印计算过程
cout << "| " << idx + 1 << " | " << v << " | ";

if (pre[v].empty()) {
cout << " 无 ";
}
else {
int max_dep = 0;
for (size_t i = 0; i < pre[v].size(); i++) {
cout << "h[" << pre[v][i] << "]=" << h[pre[v][i]];
max_dep = max(max_dep, h[pre[v][i]]);
if (i < pre[v].size() – 1) cout << ", ";
}
// 补齐空格
int spaces = 17 – (7 + 3 * pre[v].size());
for (int i = 0; i < spaces; i++) cout << " ";
}

cout << "| " << h[v] << " |" << endl;
}

cout << "+——-+———+——————-+——————-+" << endl << endl;

// 打印最终结果表
cout << "最终高度表：" << endl;
cout << "+———+———————+" << endl;
cout << "| 货物编号 | 作为顶部的最大高度 |" << endl;
cout << "+———+———————+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | " << h[i] << " |" << endl;
}
cout << "+———+———————+" << endl;
cout << "| 最大值 | " << ans << " |" << endl;
cout << "+———+———————+" << endl << endl;

return ans;
}

int main() {
cout << "========== 拓扑排序解决货物堆放问题 ==========" << endl << endl;

// 测试用例1: 有向无环图
{
cout << "【测试用例1】" << endl;
int n = 5; // 货物个数
int m = 6; // 关系数量

// pre[v] 存储可以压在货物v下的货物列表
// nex[v] 存储可以压在货物v上的货物列表
vector<vector<int>> pre(n), nex(n);

// 建立依赖关系
// 注意：这里的边方向是 u→v 表示 u可以放在v下面
pre[2].push_back(1); nex[1].push_back(2); // 1可以放在2下面
pre[1].push_back(4); nex[4].push_back(1); // 4可以放在1下面
pre[3].push_back(4); nex[4].push_back(3); // 4可以放在3下面
pre[0].push_back(2); nex[2].push_back(0); // 2可以放在0下面
pre[2].push_back(4); nex[4].push_back(2); // 4可以放在2下面
pre[0].push_back(3); nex[3].push_back(0); // 3可以放在0下面

// 打印依赖关系
cout << "货物依赖关系（方向：u→v 表示 u可以放在v下面）：" << endl;
cout << "+——-+————————-+————————-+" << endl;
cout << "| 货物编号 | 可放在下面的货物(pre) | 可放在上面的货物(nex) |" << endl;
cout << "+——-+————————-+————————-+" << endl;
for (int i = 0; i < n; i++) {
cout << "| " << i << " | ";
// 打印pre[i]
if (pre[i].empty()) {
cout << " 无 ";
}
else {
for (size_t j = 0; j < pre[i].size(); j++) {
cout << pre[i][j];
if (j < pre[i].size() – 1) cout << ", ";
}
// 补齐空格
int spaces = 21 – 3 * pre[i].size();
for (int k = 0; k < spaces; k++) cout << " ";
}
cout << "| ";
// 打印nex[i]
if (nex[i].empty()) {
cout << " 无 ";
}
else {
for (size_t j = 0; j < nex[i].size(); j++) {
cout << nex[i][j];
if (j < nex[i].size() – 1) cout << ", ";
}
// 补齐空格
int spaces = 21 – 3 * nex[i].size();
for (int k = 0; k < spaces; k++) cout << " ";
}
cout << "|" << endl;
}
cout << "+——-+————————-+————————-+" << endl << endl;

cout << "边列表（共" << m << "条）：" << endl;
cout << "(2←1), (1←4), (3←4), (0←2), (2←4), (0←3)" << endl << endl;

vector<int> permutation = TopologicalSort(n, nex);
int ans = calculate_max_height(permutation, pre);

cout << "测试用例1总结：" << endl;
cout << "货物数量: " << n << ", 关系数量: " << m << endl;
cout << "拓扑排序结果: ";
for (size_t i = 0; i < permutation.size(); i++) {
cout << permutation[i];
if (i < permutation.size() – 1) cout << " → ";
}
cout << endl << "最大堆放高度: " << ans << endl << endl;

cout << "==========================================" << endl << endl;
}

// 测试用例2: 简单链式结构
{
cout << "【测试用例2】" << endl;
int n = 4, m = 3;
vector<vector<int>> pre(n), nex(n);

pre[0].push_back(1); nex[1].push_back(0);
pre[1].push_back(2); nex[2].push_back(1);
pre[2].push_back(3); nex[3].push_back(2);

cout << "边列表（共" << m << "条）：" << endl;
cout << "(0←1), (1←2), (2←3)" << endl << endl;

vector<int> permutation = TopologicalSort(n, nex);
int ans = calculate_max_height(permutation, pre);

cout << "测试用例2总结：" << endl;
cout << "货物数量: " << n << ", 关系数量: " << m << endl;
cout << "拓扑排序结果: ";
for (size_t i = 0; i < permutation.size(); i++) {
cout << permutation[i];
if (i < permutation.size() – 1) cout << " → ";
}
cout << endl << "最大堆放高度: " << ans << endl << endl;

cout << "==========================================" << endl << endl;
}

// 测试用例3: 单个货物
{
cout << "【测试用例3】" << endl;
int n = 1, m = 0;
vector<vector<int>> pre(n), nex(n);

cout << "边列表：无" << endl << endl;

vector<int> permutation = TopologicalSort(n, nex);
int ans = calculate_max_height(permutation, pre);

cout << "测试用例3总结：" << endl;
cout << "货物数量: " << n << ", 关系数量: " << m << endl;
cout << "拓扑排序结果: ";
for (size_t i = 0; i < permutation.size(); i++) {
cout << permutation[i];
if (i < permutation.size() – 1) cout << " → ";
}
cout << endl << "最大堆放高度: " << ans << endl << endl;
}

return 0;
}

5. 输出结果

========== 拓扑排序解决货物堆放问题 ==========

【测试用例1】
货物依赖关系（方向：u→v 表示 u可以放在v下面）：
+——-+————————-+————————-+
| 货物编号 | 可放在下面的货物(pre) | 可放在上面的货物(nex) |
+——-+————————-+————————-+
| 0 | 2, 3 | 无 |
| 1 | 4 | 2 |
| 2 | 1, 4 | 0 |
| 3 | 4 | 0 |
| 4 | 无 | 1, 3, 2 |
+——-+————————-+————————-+

边列表（共6条）：
(2←1), (1←4), (3←4), (0←2), (2←4), (0←3)

拓扑排序入度表：
+———+———+
| 货物编号 | 初始入度 |
+———+———+
| 0 | 2 |
| 1 | 1 |
| 2 | 2 |
| 3 | 1 |
| 4 | 0 |
+———+———+

拓扑排序过程：
+——-+——————-+——————-+
| 步骤 | 队列中的货物 | 拓扑排序序列 |
+——-+——————-+——————-+
| 0 | 4 | 空 |
| 1 | 1, 3 | 4 |
| 2 | 3, 2 | 4 → 1 |
| 3 | 2 | 4 → 1 → 3 |
| 4 | 0 | 4 → 1 → 3 → 2 |
| 5 | 空 | 4 → 1 → 3 → 2 → 0 |
+——-+——————-+——————-+

动态规划计算过程：
+——-+———+——————-+——————-+
| 步骤 | 货物编号 | 依赖货物最大高度 | 当前货物最大高度 |
+——-+———+——————-+——————-+
| 1 | 4 | 无 | 1 |
| 2 | 1 | h[4]=1 | 2 |
| 3 | 3 | h[4]=1 | 2 |
| 4 | 2 | h[1]=2, h[4]=1 | 3 |
| 5 | 0 | h[2]=3, h[3]=2 | 4 |
+——-+———+——————-+——————-+

最终高度表：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 4 |
| 1 | 2 |
| 2 | 3 |
| 3 | 2 |
| 4 | 1 |
+———+———————+
| 最大值 | 4 |
+———+———————+

测试用例1总结：
货物数量: 5, 关系数量: 6
拓扑排序结果: 4 → 1 → 3 → 2 → 0
最大堆放高度: 4

==========================================

【测试用例2】
边列表（共3条）：
(0←1), (1←2), (2←3)

拓扑排序入度表：
+———+———+
| 货物编号 | 初始入度 |
+———+———+
| 0 | 1 |
| 1 | 1 |
| 2 | 1 |
| 3 | 0 |
+———+———+

拓扑排序过程：
+——-+——————-+——————-+
| 步骤 | 队列中的货物 | 拓扑排序序列 |
+——-+——————-+——————-+
| 0 | 3 | 空 |
| 1 | 2 | 3 |
| 2 | 1 | 3 → 2 |
| 3 | 0 | 3 → 2 → 1 |
| 4 | 空 | 3 → 2 → 1 → 0 |
+——-+——————-+——————-+

动态规划计算过程：
+——-+———+——————-+——————-+
| 步骤 | 货物编号 | 依赖货物最大高度 | 当前货物最大高度 |
+——-+———+——————-+——————-+
| 1 | 3 | 无 | 1 |
| 2 | 2 | h[3]=1 | 2 |
| 3 | 1 | h[2]=2 | 3 |
| 4 | 0 | h[1]=3 | 4 |
+——-+———+——————-+——————-+

最终高度表：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 4 |
| 1 | 3 |
| 2 | 2 |
| 3 | 1 |
+———+———————+
| 最大值 | 4 |
+———+———————+

测试用例2总结：
货物数量: 4, 关系数量: 3
拓扑排序结果: 3 → 2 → 1 → 0
最大堆放高度: 4

==========================================

【测试用例3】
边列表：无

拓扑排序入度表：
+———+———+
| 货物编号 | 初始入度 |
+———+———+
| 0 | 0 |
+———+———+

拓扑排序过程：
+——-+——————-+——————-+
| 步骤 | 队列中的货物 | 拓扑排序序列 |
+——-+——————-+——————-+
| 0 | 0 | 空 |
| 1 | 空 | 0 |
+——-+——————-+——————-+

动态规划计算过程：
+——-+———+——————-+——————-+
| 步骤 | 货物编号 | 依赖货物最大高度 | 当前货物最大高度 |
+——-+———+——————-+——————-+
| 1 | 0 | 无 | 1 |
+——-+———+——————-+——————-+

最终高度表：
+———+———————+
| 货物编号 | 作为顶部的最大高度 |
+———+———————+
| 0 | 1 |
+———+———————+
| 最大值 | 1 |
+———+———————+

测试用例3总结：
货物数量: 1, 关系数量: 0
拓扑排序结果: 0
最大堆放高度: 1

三、记忆化搜索 vs 拓扑排序

记忆化搜索 vs 拓扑排序 对比表

在货物堆放问题中的具体对比

记忆化搜索实现特点

• 优点：代码简洁，逻辑清晰
• 缺点：深度递归可能栈溢出，重复计算风险（已通过记忆化避免）

拓扑排序实现特点

• 优点：无递归，可处理大规模图
• 缺点：需额外进行拓扑排序，实现稍复杂

算法选择建议

实际应用考虑

记忆化搜索适用场景：

拓扑排序适用场景：

总结

记忆化搜索和拓扑排序都是解决有向无环图上动态规划问题的有效方法，它们本质上是同一算法的两种不同实现策略：

选择哪种方法取决于具体问题规模、实现复杂度和性能要求。对于大多数货物堆放类问题，如果图规模不大，记忆化搜索更简洁；如果图规模很大或需要处理所有节点，拓扑排序更稳定可靠。