題⽬描述

在⼀個m × n的棋盤的每⼀格都放有⼀個禮物，每個禮物都有⼀定的價值（價值⼤於 0）。你可以從棋盤的左上⻆開始拿格⼦⾥的禮物，並每次向右或者向下移動⼀格、直到到達棋盤的右下⻆。給定⼀個棋盤及其上⾯的禮物的價值，請計算你最多能拿到多少價值的禮物？

如輸⼊這樣的⼀個⼆維數組，

[
[1,3,1],
[1,5,1],
[4,2,1]
]

那麼路徑 1→3→5→2→1 可以拿到最多價值的禮物，價值為 12

思路及解答

基礎動態規劃

這道題其實⼀看就知道是動態規劃，棋盤中的每個⼩格⼦，都是和上⽅，或者左⽅的格⼦有關。既然是動態規劃，那麼我們先定義狀態：

dp[i][j]表示到達(i,j)位置時能獲得的最大禮物價值

狀態轉移：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

public int maxValue(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    
    // 初始化起點
    dp[0][0] = grid[0][0];
    
    // 初始化第一行：只能從左邊來
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 初始化第一列：只能從上邊來
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // 填充其餘位置
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    return dp[m-1][n-1];
}

每個位置的計算只依賴左邊和上邊的結果，通過雙重循環自左上向右下填充整個dp表

• 時間複雜度：O(mn)
• 空間複雜度：O(mn)

空間優化動態規劃

觀察發現當前行只依賴上一行，可以使用一維數組進行空間優化，利用dp[j]在更新前存儲上一行第j列的值，更新後存儲當前行第j列的值，實現空間複用

dp[j]表示當前行第j列的最大價值，滾動更新

public int maxValue(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    
    // 初始化第一行
    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j-1] + grid[0][j];
    }
    
    // 處理後續行
    for (int i = 1; i < m; i++) {
        // 更新第一列
        dp[0] += grid[i][0];
        
        for (int j = 1; j < n; j++) {
            // dp[j]代表上一行第j列的值（從上方來）
            // dp[j-1]代表當前行第j-1列的值（從左邊來）
            dp[j] = Math.max(dp[j], dp[j-1]) + grid[i][j];
        }
    }
    
    return dp[n-1];
}

• 時間複雜度：O(mn)
• 空間複雜度：O(n)

原地修改動態規劃（最優解）

修改原數組，直接使用grid數組作為dp表，避免額外空間分配

public int maxValue(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return 0;
    }
    
    int m = grid.length, n = grid[0].length;
    
    // 初始化第一行
    for (int j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    
    // 填充其餘位置
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
        }
    }
    
    return grid[m-1][n-1];
}

• 時間複雜度： O(nm) ，需要計算完⾥⾯的⼩格⼦
• 空間複雜度： O(1) ，優化後可以實現原地操作，不需要額外的空間