c++ - 采访: Maximum path sum in a 2-D matrix using recursion.路径恢复

Question

问题

给定一个用非负数填充的 m x n 网格，找到一条从左上角到右下角的路径，该路径最大化沿途所有数字的总和。

注意:您只能在任何时间点向下或向右移动。

方法

我刚刚用朴素的递归来解决这个问题，我为此编写的代码如下所示。我遇到的问题是我无法弄清楚如何恢复在网格中采用的路径。我通过引用(路径)传入了一个 vector ，这样我就可以恢复每个递归调用的路径。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int getMaxPath(vector<vector<int> > Grid, int r, int c, vector<int> &path)
{
    if((r > Grid.size()-1) || (c > Grid[0].size()-1))
        return 0;

    if(r==Grid.size()-1 && c==Grid[0].size()-1){
        return Grid[r][c];
    }

    int rs = getMaxPath(Grid, r, c+1, path);
    int ds = getMaxPath(Grid, r+1, c, path);


    return max(rs,ds)+Grid[r][c];

}

int maxPath(vector<vector<int> > Grid, vector<int> &path)
{
    return getMaxPath(Grid, 0, 0, path);
}

int main() {

    vector<vector<int> > mat{{5,0,8,12}, {11,16,9,13},{10,2,15,300},{3,14,18,19}};
    vector<int>path;

    path.push_back(mat[0][0]);
    int result = maxPath(mat, path);
    cout << result << endl;

    for(auto i : path)
        cout << i << " " << endl;

    return 0;
}

如你所见，代码的主要部分是递归，我会像这样放置恢复路径的行(注释)--

int getMaxPath(vector<vector<int> > Grid, int r, int c, vector<int> &path)
{
    if((r > Grid.size()-1) || (c > Grid[0].size()-1))
        return 0;

    if(r==Grid.size()-1 && c==Grid[0].size()-1){
        return Grid[r][c];
    }

    int rs = getMaxPath(Grid, r, c+1, path);
    int ds = getMaxPath(Grid, r+1, c, path);

    (rs > ds) ? path.push_back(Grid[r][c+1]) ? path.push_back(Grid[r+1][c]); // Recover path here. 
    return max(rs,ds)+Grid[r][c];

}

但我在某处遗漏了要点，因为这会导致当前元素的多个拷贝在从递归调用中缠绕和展开时进入路径。

我做错了什么？

Answer 1

由于图被编码为矩阵，每个顶点应该是一对，即 std::pair<int, int>代表(row, column)的顶点。

因此路径参数应该声明为vector<pair<int, int>>& path

int getMaxPath(vector<vector<int> > Grid, int r, int c, vector<pair<int, int>>& path)
{
    ...
    (rs > ds) ? path.emplace_back(r, c+1) : path.emplace_back(r+1, c);
}

编辑

该方法仍然不正确，因为每次递归调用，包括那些未选择(最佳)的调用，仍会将其结果放在路径中。我们需要向每个递归调用传递一个单独的 vector ，并且只有在它被选中时才将其附加到我们的 vector 中:

int getMaxPath(vector<vector<int> > Grid, int r, int c, vector<pair<int, int >> &path)
{
    if ((r > Grid.size() - 1) || (c > Grid[0].size() - 1))
        return 0;

    path.emplace_back(r, c);
    if (r == Grid.size() - 1 && c == Grid[0].size() - 1)
        return Grid[r][c];

    vector<pair<int, int >> rsPath, dsPath;
    int rs = getMaxPath(Grid, r, c + 1, rsPath);
    int ds = getMaxPath(Grid, r + 1, c, dsPath);

    if (rs > ds) {
        path.insert(path.end(), rsPath.begin(), rsPath.end());
        return rs + Grid[r][c];
    }
    else {
        path.insert(path.end(), dsPath.begin(), dsPath.end());
        return ds + Grid[r][c];
    }
}

p.s.:如您所说，如果您想捕获矩阵权重而不是坐标，您可以调整它，但遵循相同的逻辑以避免这些重复。

测试

int maxPath(vector<vector<int> > Grid, vector<pair<int, int>> &path)
{
    return getMaxPath(Grid, 0, 0, path);
}

int main()
{
        vector<vector<int> > mat{ { 5,0,8,12 },{ 11,16,9,13 },{ 10,2,15,300 },{ 3,14,18,19 } };
        vector<pair<int, int>>path;

        int result = maxPath(mat, path);
        cout << result << endl;

    for (auto it = path.begin(); it != path.end(); it++)
        std::cout << "(" << it->first << ", " << it->second << ")";
    system("pause"); return 0;
}

输出

(0, 0)(1, 0)(1, 1)(1, 2)(2, 2)(2, 3)(3, 3)