動態規劃：禮物的最大價值

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小時內刪除侵權內容。