N*M 网格中按字典顺序排列的最小路径

Question

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

Answer 1

您可以使用动态规划来解决这个问题。令为从到仅向右和向下移动的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)，返回和smallest (x, y)之间较小的字典字符串。连接两个字符串，并按词法顺序对字符串进行排序。xy+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);
}