如何优化嵌套盒子问题的DFS算法，提升效率并降低内存占用？

我遇到一个类盒子堆叠问题：给定三维尺寸的盒子，需找出最长的嵌套序列（按从大到小排序），每个盒子可像套娃一样嵌套，且盒子可进行90°倍数的旋转。我通过构建图（将能被嵌套的盒子两两相连），再采用类DFS算法从虚拟无限大盒子出发寻找最长路径的方式解决了该问题，但希望进一步提升算法运行速度并减少内存占用，恳请提供优化建议。

#include <iostream>
#include <list>
using namespace std;

struct Box {
    int h;
    int w;
    int l;
};

// Sort box dimensions from smallest to largest so then we can easily decide if some box can fit into another.
Box createBox(int h, int w, int l)
{
    if (h > l) {
        swap(h, l);
    }
    if (h > w) {
        swap(h, w);
    }
    if (w > l) {
        swap(w, l);
    }

    struct Box box = { h, w, l };
    return box;
}

// Does the second box fit in the first?
bool doesFit(Box box1, Box box2)
{
    if (box1.h > box2.h &&
        box1.w > box2.w &&
        box1.l > box2.l) {
        return true;
    }
    return false;
}

class Graph {
    int V;
    void findLongestPathUtil(int v, int path[], int& path_index);
    vector<Box> boxes;
    list<int> longest_path;
public:
    Graph(int V);
    list<int>* adj;
    void addEdge(Box b);
    int lpath_index = 0;
    void linkVertices();
    list<int> findLongestPath(int start);
};

Graph::Graph(int V)
{
    this->V = V;
    list<int> lpath(V, -1);
    longest_path = lpath;
    adj = new list<int>[V];
}

void Graph::addEdge(Box b)
{
    boxes.push_back(b);
}

// Each directed arc from node A to node B indicates that the corresponding Box A holds Box B
void Graph::linkVertices()
{
    for (int i = 0; i < V; i++) {
        for (int k = 0; k < V; k++) {
            if (doesFit(boxes[i], boxes[k])) {
                adj[i].push_back(k);
            }
        }
    }
}

list<int> Graph::findLongestPath(int start)
{
    int* path = new int[V];
    int path_index = 0;

    this->findLongestPathUtil(start, path, path_index);
    return this->longest_path;
}

void Graph::findLongestPathUtil(int v, int path[], int& path_index) {
    path[path_index] = v;
    path_index++;

    if (path_index > lpath_index) {
        int k = 0;
        for (list<int>::iterator i = longest_path.begin(); i != longest_path.end(); ++i) {
            if (k >= path_index)
                break;
            *i = path[k];
            k += 1;
        }
        lpath_index = path_index;
    }

    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
        findLongestPathUtil(*i, path, path_index);
    }

    path_index--;
}

int main()
{
    int n;
    cin >> n;
    Graph g(n + 1);
    for (int i = 0; i < n; i++) {
        int w, l, h;
        cin >> w >> l >> h;
        g.addEdge(createBox(w, l, h));
    }

    g.addEdge(createBox(INT_MAX, INT_MAX, INT_MAX));    // Infinite box
    g.linkVertices();
    list<int> path = g.findLongestPath(n);

    cout << g.lpath_index-1 << endl;    // Subtract one because path has also the infinite box
    int k = 0;
    for (auto i : path)
    {
        if (k >= g.lpath_index)
            break;
        if (k != 0)
            cout << i << endl;
        k += 1;
    }

    return 0;
}

示例输入输出 #

输入：

10 # 盒子数量
8 10 9 # 第1个盒子的长、宽、高...
9 7 10
9 10 8
7 7 9
6 1 5
2 6 4
4 5 4
6 7 10
8 6 1
3 10 10

输出：

3 # 套娃中的盒子数量
0 # 输入中的盒子索引...
3
4

优化建议 #

1. 替换图+DFS为排序+动态规划（DP） #

当前方案构建全连接图是O(n²)时间空间，对于大n开销极大。利用盒子嵌套的传递性，改用DP可大幅优化：

• 先将每个盒子的三个维度排序（你已实现createBox），再把所有盒子按h、w、l从大到小排序，确保能嵌套的盒子一定出现在被嵌套盒子的前面。
• 定义dp[i]为以第i个盒子结尾的最长嵌套序列长度，prev[i]记录前驱盒子索引用于回溯路径。
• 状态转移：dp[i] = max(dp[j] + 1) for all j < i where 盒子j能嵌套盒子i，初始dp[i] = 1。
• 最终取dp数组的最大值，通过prev数组回溯路径即可。
• 时间复杂度降为O(n²)（排序O(nlogn)，DP O(n²)），空间复杂度O(n)，远低于原方案的图内存占用。

2. 若坚持用图方案，加入记忆化搜索 #

原DFS会重复遍历相同节点的路径，加入记忆化可避免重复计算：

• 新增memo[]数组，memo[v]存储从节点v出发的最长路径长度和路径信息。
• 递归前先检查memo[v]是否已计算，若已计算直接返回结果，无需重复遍历。
• 时间复杂度从指数级降至O(n²)，空间仅增加O(n)。

3. 减少冗余处理 #

• 去重完全相同的盒子：相同尺寸的盒子无法互相嵌套，重复存在只会增加计算量，可通过排序后去重或哈希表过滤。
• 移除虚拟无限大盒子：无需实际加入数据结构，直接将所有盒子作为DP的起始点即可。

4. 内存细节优化 #

• 原Graph类中用list<int>* adj动态数组，改用vector<vector<int>> adj，避免手动内存管理，同时访问更高效。
• DFS中的int* path改用vector<int>，自动释放内存，避免泄漏。
• 存储最长路径的list<int>改用vector<int>，随机访问效率更高，复制路径时更快。

优化后的DP示例代码 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Box {
    int h, w, l;
    int original_index; // 记录输入时的原始索引
};

Box createBox(int h, int w, int l, int idx) {
    if (h > l) swap(h, l);
    if (h > w) swap(h, w);
    if (w > l) swap(w, l);
    return {h, w, l, idx};
}

bool doesFit(const Box& a, const Box& b) {
    return a.h > b.h && a.w > b.w && a.l > b.l;
}

bool compareBoxes(const Box& a, const Box& b) {
    if (a.h != b.h) return a.h > b.h;
    if (a.w != b.w) return a.w > b.w;
    return a.l > b.l;
}

int main() {
    int n;
    cin >> n;
    vector<Box> boxes;
    for (int i = 0; i < n; ++i) {
        int w, l, h;
        cin >> w >> l >> h;
        boxes.push_back(createBox(w, l, h, i));
    }

    sort(boxes.begin(), boxes.end(), compareBoxes);

    vector<int> dp(n, 1);
    vector<int> prev(n, -1);
    int max_len = 1;
    int end_idx = 0;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (doesFit(boxes[j], boxes[i]) && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            end_idx = i;
        }
    }

    // 回溯路径
    vector<int> path;
    while (end_idx != -1) {
        path.push_back(boxes[end_idx].original_index);
        end_idx = prev[end_idx];
    }
    reverse(path.begin(), path.end());

    cout << max_len << endl;
    for (int idx : path) {
        cout << idx << endl;
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者some_guy256