LC.P2304[网格中的最小路径代价]

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    int m, n;
    int[][] grid;
    int[][] moveCost;
    int[][] cache;

    public int minPathCost(int[][] grid, int[][] moveCost) {
        m = grid.length;
        n = grid[0].length;
        this.grid = grid;
        this.moveCost = moveCost;
        cache = new int[m][n];
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; ++j) {
            ans = Math.min(ans, dfs(0, j));
        }
        return ans;
    }

    private int dfs(int i, int j) {
        if (i == m - 1) return grid[i][j];
        if (cache[i][j] != 0) return cache[i][j];
        int ans = Integer.MAX_VALUE;
        for (int k = 0; k < n; ++k) {
            ans = Math.min(ans, dfs(i + 1, k) + moveCost[grid[i][j]][k]);
        }
        return cache[i][j] = ans + grid[i][j];
    }
}
  • 时间复杂度：$O(mn^2)$
  • 空间复杂度：$O(mn)$

方法二：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        f[m - 1] = grid[m - 1];
        for (int i = m - 2; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                f[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < n; ++k) {
                    f[i][j] = Math.min(f[i][j], f[i + 1][k] + moveCost[grid[i][j]][k]);
                }
                f[i][j] += grid[i][j];
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int x : f[0]) {
            ans = Math.min(ans, x);
        }
        return ans;
    }
}
  • 时间复杂度：$O(mn^2)$
  • 空间复杂度：$O(mn)$

方法三：动态规划（原地修改）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minPathCost(int[][] grid, int[][] moveCost) {
        int m = grid.length, n = grid[0].length;
        for (int i = m - 2; i >= 0; --i) {
            for (int j = 0; j < n; ++j) {
                int ans = Integer.MAX_VALUE;
                for (int k = 0; k < n; ++k) {
                    ans = Math.min(ans, grid[i + 1][k] + moveCost[grid[i][j]][k]);
                }
                grid[i][j] += ans;
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int x : grid[0]) {
            ans = Math.min(ans, x);
        }
        return ans;
    }
}
  • 时间复杂度：$O(mn^2)$
  • 空间复杂度：$O(1)$