我现在在解决CSES上的Minimal Grid Path问题，问题细节如下：

给定一个n×n的网格，每个格子包含一个大写字母。需要从左上角移动到右下角，只能向右或向下走。求能构造出的字典序最小的字符串。
输入：第一行是整数n，接下来n行是网格的每行字符串。
输出：字典序最小的路径字符串。
约束：1 ≤ n ≤ 3000

我一开始尝试用动态规划来实现，思路是维护每个格子到起点的字典序最小路径字符串。具体来说，我用prev数组逐行更新：第一行的每个位置路径就是从起点一直向右拼接字符；之后的每一行，每个位置的路径字符串取左边相邻位置或上方位置的最小字符串，再加上当前格子的字符。

以下是我的代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<string> prev;
    string s;
    cin >> s;
    prev.push_back(s.substr(0, 1));
    for (int j = 1; j < n; j++) { // 初始化第一行
        prev.push_back(prev.back() + s[j]);
    }
    for (int i = 1; i < n; i++) {
        string s;
        cin >> s;
        prev[0] += s[0]; // 处理当前行第一个元素
        for (int j = 1; j < n; j++) {
            prev[j] = min(prev[j-1], prev[j]) + s[j];
        }
    }
    cout << prev.back() << '\n';
}

不过这个解法在n较大的时候超时特别严重，完全达不到题目要求的1秒时间限制。我大概分析了一下，问题应该出在字符串的比较和拼接上：每个路径字符串的长度是O(n)级别的，每次min操作要比较两个O(n)长度的字符串，拼接也是O(n)时间，这样总时间复杂度就变成了O(n³)，对于n=3000来说，这个计算量根本跑不完。

想请教各位大佬，有没有什么优化思路？比如能不能不用存储完整的路径字符串，用其他状态来记录，避免每次都做昂贵的字符串操作？或者有没有其他更高效的DP状态定义方式？