動態(tài)規(guī)劃 禮物的最大值

題目

在一個 m*n 的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0）。你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角。給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？

示例 1:

輸入: [ [1,3,1], [1,5,1], [4,2,1] ] 輸出: 12 解釋: 路徑 1→3→5→2→1 可以拿到最多價值的禮物

提示：

0 < grid.length <= 200 0 < grid[0].length <= 200

解法

1.利用動態(tài)規(guī)劃思想，最后一個值如何獲得最大值？就是讓他的前一項是最大的，再加上他就是最大。

2.往前套，畫出表格列出公式

max[i][j]=grid[i-1][j-1]+Math.max(max[i-1][j],max[i][j-1]);

在左邊或者上邊中尋找最大值加上自身的值

3放入循環(huán)之中

4.注意事項：數(shù)組的大小應(yīng)該傳入數(shù)組的大一格，不然要加入很多判斷條件

class Solution {
    public int maxValue(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
        int max[][]=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for (int j=1;j<=m;j++){
                max[i][j]=grid[i-1][j-1]+Math.max(max[i-1][j],max[i][j-1]);
            }
        }

        
        return max[n][m]; 
    }
}