《剑指Offer》47. 礼物的最大价值

题目链接

牛客网

题目描述

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

解题思路

经典dp题目

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        if (board==null || board.length==0 || board[0].length==0) return 0;
        int m = board.length, n = board[0].length;
        int[][] dp = new int[m][n];
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0 && j==0) dp[i][j] = board[i][j];
                else if (i==0) dp[i][j] = dp[i][j-1] + board[i][j];
                else if (j==0) dp[i][j] = dp[i-1][j] + board[i][j];
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}
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];
}
《剑指Offer》47. 礼物的最大价值《剑指Offer》47. 礼物的最大价值 Melo丶 发布了216 篇原创文章 · 获赞 32 · 访问量 3万+ 私信 关注
上一篇:NOIP学习之一维数组:47.铺地毯


下一篇:nginx出现499现象及原因