剑指 Offer 47. 礼物的最大价值

剑指 Offer 47. 礼物的最大价值

• 解题思路
• 代码

解题思路

拿现在东西的最大值和前面东西的状态有关，很容易想到动态规划。

dp数组含义： dp[i][j]代表从棋盘的左上角开始，到达单元格 (i,j)下标从0开始！！ 时能拿到礼物的最大累计价值。

状态转移方程：

代码

class Solution {
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int clo = grid[0].length;

        // dp[i][j]代表从棋盘的左上角开始，到达单元格 (i,j)下标从0开始！！ 时能拿到礼物的最大累计价值。
        int[][] dp = new int[row][clo];

        //base case
        dp[0][0] = grid[0][0];
        for (int i = 1; i < clo; i++) {//初始化行是列在动，所以结尾条件是列长度
            //初始化第一行！只能从左边拿
            dp[0][i] = grid[0][i] + dp[0][i - 1];
        }
        for (int i = 1; i < row; i++) {
            //初始化第一列！只能从上边拿
            dp[i][0] = grid[i][0] + dp[i - 1][0];
        }

        //第一行、第一列已经初始化完了，直接从下标[1,1]开始
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < clo; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[row - 1][clo - 1];
    }
}