牛客JZ47 礼物的最大价值【中等动态规划 C++/Java/Go/PHP】

本文主要是介绍牛客JZ47 礼物的最大价值【中等动态规划 C++/Java/Go/PHP】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134

思路

动态规划：
每个单元格依赖于他的上边a和左边b，单元格的值为max(a,b)+自己的值

参考答案C++

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param grid int整型vector<vector<>>* @return int整型*/int maxValue(vector<vector<int> >& grid) {//简单的动态规划int n = grid.size();int m = grid[0].size();vector<vector<int>> dp(n, vector<int>(m));dp[0][0] = grid[0][0];//填充第一行for (int c = 1; c < m; c++) {dp[0][c] = dp[0][c - 1] + grid[0][c];}//填充第一列for (int r = 1; r < n; r++) {dp[r][0] = dp[r - 1][0] + grid[r][0];}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {//只能往下走或者往右，那就是每个单元格依赖于他的上边和左边int cur = dp[i - 1][j];if (cur < dp[i][j - 1]) {cur = dp[i][j - 1];}dp[i][j] = cur + grid[i][j];}}return dp[n - 1][m - 1];}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param grid int整型二维数组* @return int整型*/public int maxValue (int[][] grid) {//简单的动态规划int n = grid.length;int m = grid[0].length;int[][] dp = new int[n][m];dp[0][0] = grid[0][0];//填充第一行for (int col = 1; col < m ; col++) {dp[0][col] = dp[0][col - 1] + grid[0][col];}//填充第一列for (int row = 1; row < n ; row++) {dp[row][0] = dp[row - 1][0] + grid[row][0];}for (int i = 1; i < n ; i++) {for (int j = 1; j < m ; j++) {//只能往下走或者往右，那就是每个单元格依赖于他的上边和左边dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];}}return dp[n - 1][m - 1];}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param grid int整型二维数组* @return int整型*/
func maxValue(grid [][]int) int {//简单的动态规划n := len(grid)m := len(grid[0])dp := make([][]int, n)for i := 0; i < n; i++ {dp[i] = make([]int, m)}dp[0][0] = grid[0][0]//填充第一行for c := 1; c < m; c++ {dp[0][c] = dp[0][c-1] + grid[0][c]}//填充第一列for r := 1; r < n; r++ {dp[r][0] = dp[r-1][0] + grid[r][0]}for i := 1; i < n; i++ {for j := 1; j < m; j++ {//只能往下走或者往右，那就是每个单元格依赖于他的上边和左边cur := dp[i-1][j]if dp[i][j-1] > cur {cur = dp[i][j-1]}dp[i][j] = cur + grid[i][j]}}return dp[n-1][m-1]
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param grid int整型二维数组 * @return int整型*/
function maxValue( $grid )
{//简单的动态规划$n = count($grid);$m = count($grid[0]);$dp = [[0=>$grid[0][0]]];//填充第一行for($c = 1;$c <$m;$c++){$dp[0][$c] = $dp[0][$c-1]+$grid[0][$c];}//填充第一列for($r = 1;$r<$n;$r++){$dp[$r][0] = $dp[$r-1][0]+ $grid[$r][0];}for($i=1;$i<$n;$i++){for($j=1;$j<$m;$j++){//只能往下走或者往右，那就是每个单元格依赖于他的上边和左边$cur = $dp[$i-1][$j];if($cur < $dp[$i][$j-1]){$cur = $dp[$i][$j-1];}$dp[$i][$j] =$cur+$grid[$i][$j];}}return $dp[$n-1][$m-1];
}