AlgoPressAppearance
47-礼物的最大价值
题目描述
https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
思路: 动态规划
实现代码
csharp
public class Solution {
//动态规划
public int MaxValue(int[][] grid) {
//判断边界
if(grid.Length == 0){
return 0;
}
int maxValue = 0;
int[][] dp = new int[grid.Length+1][]; //将dp数组扩大一圈，这样左边和上边必然有数值了
for(int i=0;i<dp.Length;i++){
dp[i] = new int[grid[0].Length+1];
}
//滚动数组
//使用二维dp存放每一步的最大值
//计算到当前单元格的时候，必须保证他的左边和上边都计算好了
for(int i = 1; i <= grid.Length; i++){
for(int j = 1; j <= grid[0].Length; j++){
//状态转移方程 ：注意 dp 的取值，就是上面或者左边取最大值，不能在加入左上的值了，否则就是重复计算
// 当前单元格的最大值 = 左上的值 + 本单元格的值 + Max(上面 或者 左边)
// 为了方便边界检查 将dp数组扩大一圈
dp[i][j] = Math.Max(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
//Console.WriteLine("i:{0},j:{1},grid:{2},dp:{3}",i,j,grid[i-1][j-1],dp[i][j]);
if(dp[i][j] > maxValue){
maxValue = dp[i][j];
}
}
}
return maxValue;
}
}
复习代码实现 20220216
csharp
public class Solution {
//动态规划
//dp[i,j]表示到达这一个单元格最大的礼物价值
//因为棋子只能向右或者向下移动
//那么 dp[i,j] = max(dp[i-1,j],dp[i,j-1]);
//初始化第一行和第一列
public int MaxValue(int[][] grid) {
//扩展多一行一列，便于计算
int[,] dp = new int[grid.Length+1, grid[0].Length+1];
//状态转移
for(int i=1;i<=grid.Length;i++){
for(int j=1;j<=grid[0].Length;j++){
dp[i,j] = Math.Max(dp[i-1,j],dp[i,j-1]) + grid[i-1][j-1];
}
}
return dp[grid.Length,grid[0].Length];
}
}