algorithm - N*M 网格中字典序最小的路径

Question

我在最近的一次采访中遇到了这个问题。我们给定了一个由数字组成的 N*M 网格，网格中的一条路径是您遍历的节点。我们有一个约束，我们只能在网格中向右或向下移动。所以给定这个网格，我们需要找到lexographically 最小路径，排序后，从左上角到达网格的右下角点
例如。如果网格是 2*2
4 3
5 1
那么根据问题，按字典顺序排列的最小路径是“1 3 4”。这样的问题怎么办？代码表示赞赏。提前致谢。

Answer 1

您可以使用 Dynamic programming解决这个问题。令f(i, j)为从(i, j)到(N, M)的最小字典路径(路径排序后) > 只能向右和向下移动。考虑以下重复:

f(i, j) = sort( a(i, j) + smallest(f(i + 1, j), f(i, j + 1)))

其中 a(i, j) 是网格中 (i, j) 处的值，最小的 (x, y)返回 x 和 y 之间较小的字典字符串。 + 连接两个字符串，sort(str) 按词法顺序对字符串 str 进行排序。

递归的基本情况是:

f(N, M) = a(N, M)

当 i = N 或 j = M 时，循环也会发生变化(确保您看到了)。

考虑以下用 C++ 编写的代码:

//-- the 200 is just the array size. It can be modified

string a[200][200];             //-- represent the input grid
string f[200][200];             //-- represent the array used for memoization
bool calculated[200][200];      //-- false if we have not calculate the value before, and true if we have
int N = 199, M = 199;           //-- Number of rows, Number of columns


//-- sort the string str and return it
string srt(string &str){
    sort(str.begin(), str.end());
    return str;
}


//-- return the smallest of x and y
string smallest(string & x, string &y){
    for (int i = 0; i < x.size(); i++){
        if (x[i] < y[i]) return x;
        if (x[i] > y[i]) return y;
    }
    return x;
}



string solve(int i, int j){
    if (i == N && j == M) return a[i][j];       //-- if we have reached the buttom right cell (I assumed the array is 1-indexed
    if (calculated[i][j]) return f[i][j];       //-- if we have calculated this before 
    string ans;
    if (i == N) ans = srt(a[i][j] + solve(i, j + 1));       //-- if we are at the buttom boundary
    else if (j == M) ans = srt(a[i][j] + solve(i + 1, j));  //-- if we are at the right boundary
    else ans = srt(a[i][j] + smallest(solve(i, j + 1), solve(i + 1, j)));       
    calculated[i][j] = true;        //-- to fetch the calculated result in future calls
    f[i][j] = ans;
    return ans;
}


string calculateSmallestPath(){
    return solve(1, 1);
}