礼物的最大价值
题目形容
在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有肯定价值（大于 0）。从左上角开始拿礼物，每次向右或向下挪动一格，直到右下角完结。
- 给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘
- 1 10 3 8
- 12 2 9 6
- 5 7 4 11
- 3 7 16 5
- 礼物的最大价值为 1+12+5+7+7+16+5=53。
题目链接: [礼物的最大价值]()
代码
/** * 题目：礼物的最大价值 * 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有肯定价值（大于 0）。从左上角开始拿礼物，每次向右或向下挪动一格，直到右下角完结。 * 给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘 * 1 10 3 8 * 12 2 9 6 * 5 7 4 11 * 3 7 16 5 * 礼物的最大价值为 1+12+5+7+7+16+5=53。 */public class Jz72 { /** * 动静布局 * * @param values * @return */ public int getMost(int[][] values) { if (values == null || values.length == 0 || values[0].length == 0) { return 0; } int n = values[0].length; int[] dp = new int[n]; for (int[] value : values) { dp[0] += value[0]; for (int i = 1; i < n; i++) { dp[i] = Math.max(dp[i], dp[i - 1]) + value[i]; } } return dp[n - 1]; } public static void main(String[] args) { int[][] values = new int[][]{{1, 10, 3, 8}, {12, 2, 9, 6}, {5, 7, 4, 11}, {3, 7, 16, 5}}; Jz72 jz72 = new Jz72(); System.out.println(jz72.getMost(values)); }}【每日寄语】 玉不琢，不成器；人不学，不知义。