如何优化基于动态规划的运算符括号化求解算法效率？

运算表示例：1⊕2 = 2

我正在解决一个动态规划问题：给定一张运算符表，以及一个无括号的运算序列（例如2⊕2⊕2⊕2⊕1⊕3），需要判断是否可通过添加括号改变运算顺序，使序列运算结果等于预期值（如1），同时需找到最左侧的合法括号化方式（示例：((((2⊕2)⊕2)⊕(2⊕1))⊕3) = 1）。

我已实现一种DP解法，通过构建DP表计算所有子序列的可能结果及对应表达式，但该方法会枚举所有解，处理较大输入时效率极低。请问如何优化该算法以提升运行速度？以下是相关代码：

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 存储运算结果及对应表达式的结构体
struct Result {
    int value;
    string expression;
};

int main() {
    // 优化cin/cout性能
    ios::sync_with_stdio(0);
    cin.tie(0); 

    int n, m;
    cin >> n >> m; // 读取运算表维度n和序列长度m

    // 读取运算表
    vector<vector<int>> table(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> table[i][j];
        }
    }

    // 读取运算序列
    vector<int> sequence(m);
    for (int i = 0; i < m; ++i) {
        cin >> sequence[i];
    }

    // 读取预期结果
    int expectedResult;
    cin >> expectedResult;

    // 初始化DP表
    vector<vector<vector<Result>>> dp(m, vector<vector<Result>>(m));

    // 填充基础情况（长度为1的子序列）
    for (int i = 0; i < m; ++i) {
        dp[i][i].push_back({sequence[i], to_string(sequence[i])});
    }

    // 填充长度大于1的子序列
    for (int len = 2; len <= m; ++len) { // 子序列长度（最小为2）
        for (int i = 0; i <= m - len; ++i) { // 子序列起始位置
            int j = i + len - 1; // 子序列结束位置
            for (int k = i; k < j; ++k) { // 分割点，将子序列分为[i,k]和[k+1,j]
                for (const auto &left : dp[i][k]) {
                    for (const auto &right : dp[k + 1][j]) {
                        int result = table[left.value - 1][right.value - 1];
                        string expr = "(" + left.expression + " " + right.expression + ")"; 
                        dp[i][j].push_back({result, expr});
                    }
                }
            }
        }
    }

    // 筛选出结果等于预期值的表达式（取最后找到的一个）
    string lastValidExpression = "";
    for (const auto &res : dp[0][m - 1]) {
        if (res.value == expectedResult) {
            lastValidExpression = res.expression; // 更新为最新找到的表达式
        }
    }

    // 输出结果
    if (!lastValidExpression.empty()) {
        cout << "1\n" << lastValidExpression << endl;
    } else {
        cout << "0" << endl;
    }

    return 0;
}

输入输出示例 #

示例1 #

输入：

2 4
1 2
2 1
1 2 2 1
1

输出：

1 
(((1 2) 2) 1)

示例2 #

输入：

3 6
3 2 1
3 2 1
1 3 3
2 2 2 2 1 3
1

输出：

1
((((2 2) 2) (2 1)) 3)

优化方案 #

当前实现的最大问题是存储了同一子序列的所有可能结果及表达式，导致空间和时间复杂度爆炸（时间复杂度为O(m³*K²)，K是每个子序列的可能结果数）。以下是针对性优化：

1. 去重存储：同一值只保留最左侧的表达式 #

对于每个子区间[i,j]，不需要存储所有能得到某个值的表达式，只需要保留首次得到该值的表达式（因为我们要找最左侧的合法括号化方式，优先左侧分割点的解）。这样可以大幅减少DP表中的元素数量。

修改方式：将dp[i][j]从vector<Result>改为unordered_map<int, string>，键是运算结果值，值是对应的最左侧表达式。当计算出一个值时，如果该值不在map中，才存入对应的表达式；如果已存在，直接跳过（因为首次存入的就是最左侧的解）。

2. 提前终止：一旦找到目标结果可提前退出 #

在填充DP表的过程中，如果当前处理的区间是[0, m-1]且已经找到预期结果，可以提前终止计算，无需继续枚举所有可能。

3. 避免不必要的字符串拼接（可选） #

字符串拼接是耗时操作，我们可以只存储括号化的结构信息（比如分割点），最后再根据结构生成表达式，而不是在DP过程中实时拼接字符串。不过这个优化对代码改动较大，优先考虑前两个优化。

优化后的代码示例 #

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); 

    int n, m;
    cin >> n >> m;

    vector<vector<int>> table(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> table[i][j];
        }
    }

    vector<int> sequence(m);
    for (int i = 0; i < m; ++i) {
        cin >> sequence[i];
    }

    int expectedResult;
    cin >> expectedResult;

    // 优化：用unordered_map存储每个区间的{结果值: 最左侧表达式}
    vector<vector<unordered_map<int, string>>> dp(m, vector<unordered_map<int, string>>(m));

    // 基础情况
    for (int i = 0; i < m; ++i) {
        dp[i][i][sequence[i]] = to_string(sequence[i]);
    }

    bool found = false;
    for (int len = 2; len <= m; ++len) {
        if (found) break; // 找到目标结果提前终止
        for (int i = 0; i <= m - len; ++i) {
            int j = i + len - 1;
            // 优先遍历左侧分割点，保证首次存入的是最左侧表达式
            for (int k = i; k < j; ++k) {
                for (const auto &left_pair : dp[i][k]) {
                    int left_val = left_pair.first;
                    const string &left_expr = left_pair.second;
                    for (const auto &right_pair : dp[k+1][j]) {
                        int right_val = right_pair.first;
                        const string &right_expr = right_pair.second;
                        int res_val = table[left_val - 1][right_val - 1];
                        // 只有当该值未被记录时才存入，保证最左侧的表达式
                        if (dp[i][j].find(res_val) == dp[i][j].end()) {
                            dp[i][j][res_val] = "(" + left_expr + " " + right_expr + ")";
                            // 如果是整个序列且找到预期结果，标记提前终止
                            if (i == 0 && j == m-1 && res_val == expectedResult) {
                                found = true;
                                goto end_loop; // 跳出所有循环
                            }
                        }
                    }
                }
            }
        }
    }
end_loop:

    auto &final_map = dp[0][m-1];
    if (final_map.find(expectedResult) != final_map.end()) {
        cout << "1\n" << final_map[expectedResult] << endl;
    } else {
        cout << "0" << endl;
    }

    return 0;
}

优化效果说明 #

• 空间上：每个区间只存储唯一值对应的表达式，避免了大量重复数据，空间复杂度从O(m²K)降至O(m²V)，其中V是运算结果的可能取值数量（远小于K）。
• 时间上：减少了大量重复计算和字符串操作，同时提前终止机制可以在找到解后立即停止，大幅提升大输入下的运行速度。
• 正确性：由于优先遍历左侧分割点，且同一值只保留首次存入的表达式，确保了得到的是最左侧的合法括号化方式。

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