[劍指offer]面試題第[47]題[JAVA][禮物的最大價值][動态規劃]

【問題描述】[中等]

【解答思路】

1動态規劃

動态規劃流程

第 1 步：設計狀态

f(i, j)f(i,j) 為從棋盤左上角走至單元格 (i ,j)(i,j) 的禮物最大累計價值

第 2 步：狀态轉移方程

f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j)

第 3 步：考慮初始化

第 4 步：考慮輸出

第 5 步：考慮是否可以狀态壓縮

時間複雜度：O(N^2) 空間複雜度：O(1)

class Solution {
    public int maxValue(int[][] grid) {
    //m 列數 n 行數
        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][j - 1], grid[i - 1][j]);
        return grid[m - 1][n - 1];
    }
}


           

【總結】

1. 動态規劃流程

第 1 步：設計狀态

第 2 步：狀态轉移方程

第 3 步：考慮初始化

第 4 步：考慮輸出

第 5 步：考慮是否可以狀态壓縮

2. 壓縮空間可以在原數組上操作 行列

3.想清楚應該加什麼，切忌想當然

3.類似題目[Leetcode][第64題][JAVA][64. 最小路徑和]

轉載連結：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/solution/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/