JZ-072-礼物的最大价值 java算法动态规划

礼物的最大价值题目描述

在一个 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。

【JZ-072-礼物的最大价值】题目链接: [礼物的最大价值]()

代码

/** * 标题：礼物的最大价值 * 在一个 m*n 的棋盘的每一个格都放有一个礼物，每个礼物都有一定价值（大于 0）。从左上角开始拿礼物，每次向右或向下移动一格，直到右下角结束。 * 给定一个棋盘，求拿到礼物的最大价值。例如，对于如下棋盘 * 11038 * 12296 * 57411 * 37165 * 礼物的最大价值为 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)); } }