JZ47 禮物的最大價值
描述
描述
在一個m\times nm×n的棋盤的每一格都放有一個禮物，每個禮物都有一定的價值（價值大于 0），你可以從棋盤的左上角開始拿格子里的禮物，并每次向右或者向下移動一格、直到到達棋盤的右下角，給定一個棋盤及其上面的禮物的價值，請計算你最多能拿到多少價值的禮物？
如輸入這樣的一個二維陣列，
[
[1,3,1],
[1,5,1],
[4,2,1]
]
那么路徑 1→3→5→2→1 可以拿到最多價值的禮物，價值為12
具體做法：
step 1：初始化第一列，每個元素只能累加自上方，
step 2：初始化第一行，每個元素只能累加自左方，
step 3：然后遍歷陣列，對于每個元素添加來自上方或者左方的較大值，
代碼
package mid.JZ47禮物的最大價值;
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
*
* @param grid int整型二維陣列
* @return int整型
*/
public int maxValue (int[][] grid) {
// write code here
int x = grid[0].length;
int y = grid.length;
//初始化第一列
for (int i = 1; i < y; i++) {
grid[i][0] += grid[i - 1][0];
}
//初始化第一行
for (int i = 1; i < x; i++) {
grid[0][i] += grid[0][i - 1];
}
for (int i = 1; i < y; i++) {
for (int j = 1; j < x; j++) {
grid[i][j] += Math.max(grid[i-1][j], grid[i][j-1]);
}
}
return grid[y-1][x-1];
}
public static void main(String[] args) {
int[][] ints = {{9, 1, 4, 8}};
System.out.println(new Solution().maxValue(ints));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540266.html
標籤：其他
下一篇：狀態機的實作