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

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]; } }

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。