动态规划：礼物的最大价值

package com.nobody;

/**
 * 题目：
 * 礼物的最大价值
 * 描述：
 * 在一个 m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋
 * 盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 * 示例：
 * 输入:
 * [
 * [1,3,1],
 * [1,5,1],
 * [4,2,1]
 * ]
 * 输出: 12
 * 路径 1→3→5→2→1
 * @author Μr.ηobοdy
 *
 * @date 2020-03-29
 *
 */
public class MaxValue { // 动态规划 // 假设dp[row][col]是走到[row][col]位置时的最大价值 // 走到[row][col]位置有2种情况，一种为从[row][col-1]位置往右走，一种为从[row-1][col]位置往下走 // 数组的第0行每一个位置只能从左边走过来，第0列每一个位置只能从上边走过来，故可以优先初始化处理 public int maxValue(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int[][] dp = new int[rows][cols]; dp[0][0] = grid[0][0]; // 处理第0行 for (int col = 1; col < cols; col++) { dp[0][col] = dp[0][col-1] + grid[0][col]; } // 处理第0列 for (int row = 1; row < rows; row++) { dp[row][0] = dp[row-1][0] + grid[row][0]; } // 处理其他行列 for (int row = 1; row < rows; row++) { for (int col = 1; col < cols; col++) { dp[row][col] = Math.max(dp[row][col-1], dp[row-1][col]) + grid[row][col]; } } return dp[rows-1][cols-1]; } // 动态规划,优化版 // 走到[row][col]位置有2种情况，一种为从[row][col-1]位置往右走，一种为从[row-1][col]位置往下走 // 故row-2行以上的数据没有必要保存下来，使用一维数组maxValues[cols]保存： // maxValues[0]到maxValues[col-1]保存当前行0到col-1列的最大价值 // maxValues[col]到maxValues[cols-1]保存上一行col列到cols-1列的最大价值 // 计算grid[row][col]当前位置的最大价值后，将最大价值值存入maxValues[col]中 public int maxValue1(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int[] maxValues = new int[cols]; // 记录当前位置左边位置的最大价值 int leftMaxValue = 0; // 记录当前位置上边位置的最大价值 int upMaxValue = 0; // 遍历每一个位置 for (int row = 0; row < rows; row++) { for (int col = 0; col < cols; col++) { leftMaxValue = 0; upMaxValue = 0; if (row > 0) { upMaxValue = maxValues[col]; } if (col > 0) { leftMaxValue = maxValues[col-1]; } maxValues[col] = Math.max(upMaxValue, leftMaxValue) + grid[row][col]; } } return maxValues[cols-1]; }

}

文章来源: javalib.blog.csdn.net，作者：陈皮的JavaLib，版权归原作者所有，如需转载，请联系作者。

原文链接：javalib.blog.csdn.net/article/details/105172545