求首尾循环连通最长整数的高效解法（DFS超时优化）

问题重述 #

给定一组整数（数量<100000），满足以下规则可连接：

1. 前一个数的最后一位与后一个数的第一位相同；
2. 后一个数必须位于原数组中前一个数的后方（即下标更大）。
   需要找出首尾数字相同的最长连通整数链的总位数。

现有DFS解法的问题 #

你的DFS实现采用递归枚举所有可能的链组合，时间复杂度为O(2^N)，当N=5000时，分支数量呈指数级增长，完全无法在6秒内完成计算，必须采用更高效的动态规划思路。

另外，你的代码中get_num_digit函数存在未初始化变量的问题：int i;未赋值，当输入数字小于10时，会返回随机值，需要修正为int i=0;。

动态规划优化思路 #

由于每个数的首尾数字只能是0-9，我们可以利用这个特性压缩状态，将问题的时间复杂度降至O(N*10)，完全适配1e5级别的数据量：

1. 状态定义：使用一个10×10的二维数组dp，其中dp[start][end]表示当前已处理的数中，以start开头、end结尾的连通链的最大总位数。
2. 状态转移：
   • 对于每个数（首数字f、尾数字l、长度len）：
     • 首先考虑单独选择该数的情况：如果len大于当前dp[f][l]，则更新dp[f][l] = len。
     • 然后考虑将该数接在已有链的后面：遍历所有可能的前置链结尾数字prev_end（0-9），若prev_end == f，则对于每个prev_start，若dp[prev_start][prev_end] + len大于当前dp[prev_start][l]，则更新dp[prev_start][l]为该值。
   • 每次更新状态后，检查所有dp[s][s]（首尾相同的链）的最大值，维护全局结果。

优化后的代码实现 #

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using ull = unsigned long long;

int get_first_digit(ull n) {
    while (n >= 10) n /= 10;
    return n;
}

int get_last_digit(ull n) {
    return n % 10;
}

int get_num_digit(ull n) {
    if (n == 0) return 1;
    int i = 0;
    while (n >= 10) {
        n /= 10;
        i++;
    }
    return i + 1;
}

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

    ull N;
    cin >> N;

    // dp[start][end]：以start开头、end结尾的最长链长度
    int dp[10][10] = {0};
    int result = 0;

    for (ull i = 0; i < N; ++i) {
        ull num;
        cin >> num;
        int f = get_first_digit(num);
        int l = get_last_digit(num);
        int len = get_num_digit(num);

        // 临时数组存储新状态，避免覆盖当前遍历的状态
        int temp[10][10];
        memcpy(temp, dp, sizeof(dp));

        // 情况1：单独选当前数
        if (len > temp[f][l]) {
            temp[f][l] = len;
        }

        // 情况2：接在已有链后面
        for (int prev_end = 0; prev_end < 10; ++prev_end) {
            if (prev_end != f) continue;
            for (int prev_start = 0; prev_start < 10; ++prev_start) {
                if (dp[prev_start][prev_end] == 0) continue;
                if (dp[prev_start][prev_end] + len > temp[prev_start][l]) {
                    temp[prev_start][l] = dp[prev_start][prev_end] + len;
                }
            }
        }

        // 更新dp数组
        memcpy(dp, temp, sizeof(temp));

        // 更新首尾相同的最长链长度
        for (int s = 0; s < 10; ++s) {
            if (dp[s][s] > result) {
                result = dp[s][s];
            }
        }
    }

    cout << result << endl;

    return 0;
}

代码说明 #

• 使用ios::sync_with_stdio(false); cin.tie(nullptr);加速输入，适配大数据量的读取。
• 引入临时数组temp存储新状态，避免在遍历过程中覆盖原dp值导致计算错误。
• 修正了get_num_digit函数的未初始化问题，同时处理了n=0的特殊情况。
• 每次处理完一个数后，立即更新全局结果，确保不会遗漏可能的最长链。

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