java - M x N 矩阵中长度为 K 的最大得分路径

Question

在处理另一个问题时，我遇到了这个问题:

Given a matrix and an integer k, find the path of length k within the matrix that maximizes the sum of the cells in the path. The path can start at any cell, can proceed in any direction, and can turn freely at each point. The path can also intersect itself, but if it does, a given cell only counts once toward the sum.

Return the sum.

为了解决这个问题，我尝试了一种递归方法，其中对于每个可能的起始位置(即矩阵的所有元素)我计算可能的最长路径并尝试使用查找表以便重复某个点在网格中产生 0 值。问题是我不确定如何以及何时重新初始化查找表，这样我就不会丢失可能的路线。

到目前为止，我的实现看起来像这样。

    int maxP(int i, int j, int steps, int[][] grid) {
        if (i < 0 || i >= n || j < 0 || j >= m || steps < 0) {
            return 0;
        }
        // check if place has been passed through before
        int cost;
        if (lookup[i][j] == 1) {
           cost = 0;
        } else {
           cost = grid[i][j];
           lookup[i][j] = 1;
       }

       return cost + max(
            maxP(i - 1, j - 1, steps - 1, grid),
            maxP(i - 1, j, steps - 1, grid),
            maxP(i - 1, j + 1,steps - 1, grid),
            maxP(i, j - 1,  steps - 1, grid),
            maxP(i, j + 1, steps - 1, grid),
            maxP(i + 1, j - 1, steps - 1, grid),
            maxP(i + 1, j, steps - 1, grid),
            maxP(i + 1, j + 1, steps - 1, grid)
       );
}

Answer 1

“如何以及何时重新初始化查找表”的答案是 lookup[i][j] 需要计算多少次访问了一个网格位置。输入网格位置时，增加计数。回溯时，递减计数。也就是说，您永远不会“重新初始化查找表”。您始终以增量方式维护表格。

修改后的代码如下:

int maxP(int i, int j, int steps, int[][] grid) {
    if (i < 0 || i >= n || j < 0 || j >= m || steps < 0) {
        return 0;
    }
    // check if place has been passed through before
    int cost = 0;
    if (lookup[i][j] == 0) {
        cost = grid[i][j];
    }

    // mark this place as visited
    lookup[i][j]++;

    // find the best cost recursively
    cost = cost + max(
                      maxP(i - 1, j - 1, steps - 1, grid),
                      maxP(i - 1, j, steps - 1, grid),
                      maxP(i - 1, j + 1,steps - 1, grid),
                      maxP(i, j - 1,  steps - 1, grid),
                      maxP(i, j + 1, steps - 1, grid),
                      maxP(i + 1, j - 1, steps - 1, grid),
                      maxP(i + 1, j, steps - 1, grid),
                      maxP(i + 1, j + 1, steps - 1, grid)
                      );

    // undo the change to the lookup table
    lookup[i][j]--;

    return cost;
}