登录3742. 网格中得分最大的路径
解法
思路和算法
由于每次只能向右或者向下移动，对于每个值为 $0$ 的单元格花费 $0$，对于每个值为 $1$ 的单元格花费 $1$，因此对于网格中的每个单元格，到达该单元格的路径的最大分数需要通过到达相邻单元格的路径的最大分数与花费计算得到。可以使用动态规划计算最大分数。
网格 $\textit{grid}$ 的网格 $\textit{coins}$ 的大小是 $m \times n$。创建 $m \times n \times (k + 1)$ 的三维数组 $\textit{dp}$，其中 $\textit{dp}[i][j][c]$ 表示从单元格 $(0, 0)$ 到达单元格 $(i, j)$ 且花费不超过 $c$ 的最大分数，对于不可能的状态使用 $-\infty$ 表示。由于花费一定非负，因此为方便处理，规定当 $c < 0$ 时 $\textit{dp}[i][j][c] = -\infty$，表示不可能的状态。
当 $i = 0$ 且 $j = 0$ 时，路径上只有 $(0, 0)$ 一个位置，根据 $\textit{grid}[0][0] = 0$ 可以得到分数是 $0$ 且花费是 $0$，因此动态规划的边界情况是：对于任意 $0 \le c \le k$，$\textit{dp}[0][0][c] = 0$。
当 $i > 0$ 或 $j > 0$ 时，计算 $\textit{dp}[i][j][c]$ 需要考虑到达相邻单元格的路径的最大分数与花费。定义示性函数 $\mathbb{I}(b)$，当 $b = \text{true}$ 时 $\mathbb{I}(b) = 1$，当 $b = \text{false}$ 时 $\mathbb{I}(b) = 0$。
-
当 $i = 0$ 且 $j > 0$ 时，只能从 $(i, j - 1)$ 向右移动到 $(i, j)$，因此 $\textit{dp}[i][j][c] = \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[0][j] \ne 0)] + \textit{grid}[i][j]$。
-
当 $i > 0$ 且 $j = 0$ 时，只能从 $(i - 1, j)$ 向下移动到 $(i, j)$，因此 $\textit{dp}[i][j][c] = \textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][0] \ne 0)] + \textit{grid}[i][j]$。
-
当 $i > 0$ 且 $j > 0$ 时，可以从 $(i - 1, j)$ 向下移动到 $(i, j)$ 或从 $(i, j - 1)$ 向右移动到 $(i, j)$，到达 $(i, j)$ 的路径的最大分数为其中的最大值，因此 $\textit{dp}[i][j][c] = \max(\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)], \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)]) + \textit{grid}[i][j])$。
根据上述分析，当 $i > 0$ 或 $j > 0$ 时，动态规划的状态转移方程如下。
$$
\textit{dp}[i][j][c] = \begin{cases}
\textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[0][j] \ne 0)] + \textit{grid}[i][j], & i = 0 \wedge j > 0 \
\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][0] \ne 0)] + \textit{grid}[i][j], & i > 0 \wedge j = 0 \
\max(\textit{dp}[i - 1][j][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)], \textit{dp}[i][j - 1][c - \mathbb{I}(\textit{grid}[i][j] \ne 0)]) + \textit{grid}[i][j]), & i > 0 \wedge j > 0
\end{cases}
$$
根据动态规划的状态转移方程，计算 $\textit{dp}[i][j]$ 的顺序可以是以下两种。
-
从小到大遍历每个 $i$，对于每个 $i$ 从小到大遍历每个 $j$。该顺序为按行遍历。
-
从小到大遍历每个 $j$，对于每个 $j$ 从小到大遍历每个 $i$。该顺序为按列遍历。
计算得到 $\textit{dp}[m - 1][n - 1][k]$ 即为从左上角到右下角的总花费不超过 $k$ 的最大分数。
上述做法的时间复杂度和空间复杂度都是 $O(mnk)$。
实现方面可以优化空间，按行遍历和按列遍历的优化空间做法分别如下。
-
按行遍历时，由于 $\textit{dp}[i][]$ 只取决于 $\textit{dp}[i - 1][]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一行的状态，将空间复杂度降到 $O(n)$。
-
按列遍历时，由于 $\textit{dp}[][j]$ 只取决于 $\textit{dp}[][j - 1]$，和更早的状态无关，因此可以使用滚动数组的思想，只保留前一列的状态，将空间复杂度降到 $O(m)$。
使用优化空间做法时，对于每个单元格 $(i, j)$ 计算状态值时应从大到小遍历每个 $c$。
当 $m \ge n$ 时可以使用按行遍历，当 $m < n$ 时可以使用按列遍历，将空间复杂度降到 $O(\min(m, n) \times k)$。
代码
下面的代码为不优化空间的实现。
###Java
class Solution {
public int maxPathScore(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][][] dp = new int[m][n][k + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
Arrays.fill(dp[i][j], Integer.MIN_VALUE);
}
}
Arrays.fill(dp[0][0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[0][j][c] = dp[0][j - 1][c - costIncrease] + grid[0][j];
}
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][0][c] = dp[i - 1][0][c - costIncrease] + grid[i][0];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][j][c] = Math.max(dp[i - 1][j][c - costIncrease], dp[i][j - 1][c - costIncrease]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1][k] >= 0 ? dp[m - 1][n - 1][k] : -1;
}
}
###C#
public class Solution {
public int MaxPathScore(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][][] dp = new int[m][][];
for (int i = 0; i < m; i++) {
dp[i] = new int[n][];
for (int j = 0; j < n; j++) {
dp[i][j] = new int[k + 1];
Array.Fill(dp[i][j], int.MinValue);
}
}
Array.Fill(dp[0][0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[0][j][c] = dp[0][j - 1][c - costIncrease] + grid[0][j];
}
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][0][c] = dp[i - 1][0][c - costIncrease] + grid[i][0];
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = costIncrease; c <= k; c++) {
dp[i][j][c] = Math.Max(dp[i - 1][j][c - costIncrease], dp[i][j - 1][c - costIncrease]) + grid[i][j];
}
}
}
return dp[m - 1][n - 1][k] >= 0 ? dp[m - 1][n - 1][k] : -1;
}
}
下面的代码为优化空间的实现。
###Java
class Solution {
public int maxPathScore(int[][] grid, int k) {
return grid.length >= grid[0].length ? maxPathScoreHorizontal(grid, k) : maxPathScoreVertical(grid, k);
}
public int maxPathScoreHorizontal(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[n][k + 1];
for (int j = 0; j < n; j++) {
Arrays.fill(dp[j], Integer.MIN_VALUE);
}
Arrays.fill(dp[0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? dp[j - 1][c - costIncrease] + grid[0][j] : Integer.MIN_VALUE;
}
}
for (int i = 1; i < m; i++) {
int costIncrease0 = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[i][0] : Integer.MIN_VALUE;
}
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? Math.max(dp[j][c - costIncrease], dp[j - 1][c - costIncrease]) + grid[i][j] : Integer.MIN_VALUE;
}
}
}
return dp[n - 1][k] >= 0 ? dp[n - 1][k] : -1;
}
public int maxPathScoreVertical(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][k + 1];
for (int i = 0; i < m; i++) {
Arrays.fill(dp[i], Integer.MIN_VALUE);
}
Arrays.fill(dp[0], 0);
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? dp[i - 1][c - costIncrease] + grid[i][0] : Integer.MIN_VALUE;
}
}
for (int j = 1; j < n; j++) {
int costIncrease0 = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[0][j] : Integer.MIN_VALUE;
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? Math.max(dp[i][c - costIncrease], dp[i - 1][c - costIncrease]) + grid[i][j] : Integer.MIN_VALUE;
}
}
}
return dp[m - 1][k] >= 0 ? dp[m - 1][k] : -1;
}
}
###C#
public class Solution {
public int MaxPathScore(int[][] grid, int k) {
return grid.Length >= grid[0].Length ? MaxPathScoreHorizontal(grid, k) : MaxPathScoreVertical(grid, k);
}
public int MaxPathScoreHorizontal(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][] dp = new int[n][];
for (int j = 0; j < n; j++) {
dp[j] = new int[k + 1];
Array.Fill(dp[j], int.MinValue);
}
Array.Fill(dp[0], 0);
for (int j = 1; j < n; j++) {
int costIncrease = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? dp[j - 1][c - costIncrease] + grid[0][j] : int.MinValue;
}
}
for (int i = 1; i < m; i++) {
int costIncrease0 = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[i][0] : int.MinValue;
}
for (int j = 1; j < n; j++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[j][c] = c >= costIncrease ? Math.Max(dp[j][c - costIncrease], dp[j - 1][c - costIncrease]) + grid[i][j] : int.MinValue;
}
}
}
return dp[n - 1][k] >= 0 ? dp[n - 1][k] : -1;
}
public int MaxPathScoreVertical(int[][] grid, int k) {
int m = grid.Length, n = grid[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) {
dp[i] = new int[k + 1];
Array.Fill(dp[i], int.MinValue);
}
Array.Fill(dp[0], 0);
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][0] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? dp[i - 1][c - costIncrease] + grid[i][0] : int.MinValue;
}
}
for (int j = 1; j < n; j++) {
int costIncrease0 = grid[0][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[0][c] = c >= costIncrease0 ? dp[0][c - costIncrease0] + grid[0][j] : int.MinValue;
}
for (int i = 1; i < m; i++) {
int costIncrease = grid[i][j] != 0 ? 1 : 0;
for (int c = k; c >= 0; c--) {
dp[i][c] = c >= costIncrease ? Math.Max(dp[i][c - costIncrease], dp[i - 1][c - costIncrease]) + grid[i][j] : int.MinValue;
}
}
}
return dp[m - 1][k] >= 0 ? dp[m - 1][k] : -1;
}
}
复杂度分析
-
时间复杂度：$O(mnk)$，其中 $m$ 和 $n$ 分别是网格 $\textit{grid}$ 的行数和列数，$k$ 是总花费上限。动态规划的状态数是 $O(mnk)$，每个状态的计算时间是 $O(1)$，因此时间复杂度是 $O(mnk)$。
-
空间复杂度：$O(mnk)$ 或 $O(\min(m, n) \times k)$，其中 $m$ 和 $n$ 分别是网格 $\textit{grid}$ 的行数和列数，$k$ 是总花费上限。空间复杂度取决于实现方式，不优化空间的实现需要创建大小为 $m \times n \times (k + 1)$ 的三维数组因此空间复杂度是 $O(mnk)$，优化空间的实现需要创建大小为 $\min(m, n) \times (k + 1)$ 的二维数组因此空间复杂度是 $O(\min(m, n) \times k)$。
