礼物的最大价值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型二维数组 
     * @return int整型
     */
    public int maxValue (int[][] grid) {
        // write code here
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(i == 0 && j == 0) continue;
                if(i == 0) grid[i][j] += grid[i][j - 1];       // 上边界，只能从左边来
                else if(j == 0) grid[i][j] += grid[i -1][j];   // 左边界，只能从上边来
                else grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);    // 其他情况选择从上和从左来中更大的那个
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

//二维动态规划，创建一个dp二维数组，长度比grid大一
//dp中存放对应的grid数组中走到这个位置的礼物最大价值，
//状态转移方程：
//dp[i][j] = Math.max( dp[i-1][j] + grid[i-1][j-1], dp[i][j-1] + grid[i-1][j-1])
import java.util.*;

public class Solution {
    public int maxValue (int[][] grid) {
        int[][] dp = new int[grid.length+1][grid[0].length+1];
        for(int i = 1; i < dp.length ; i++){
            for(int j = 1 ; j < dp[0].length ; j++){
                dp[i][j] = Math.max(dp[i-1][j]+grid[i-1][j-1],dp[i][j-1]+grid[i-1][j-1]);
            }
        }
        return dp[grid.length][grid[0].length];
    }
}

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        for i in range(1, m):
            for j in range(1, n):
                if i < m and j < n:
                    dp[i][j] = max(dp[i][j - 1] + grid[i][j], dp[i - 1][j] + grid[i][j])
        return dp[m - 1][n - 1]

function maxValue(grid) {
    // write code here
    let n = grid.length;
    let m = grid[0].length;
    let dp = [];
    for (let i = 0; i < n; i++) {
        dp[i] = [];
    }
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (j === 0 && i === 0) {
                dp[i][j] = grid[0][0];
            } else if (i === 0) {
                dp[i][j] = dp[i][j - 1] + grid[i][j];
            } else if (j === 0) {
                dp[i][j] = dp[i - 1][j] + grid[i][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
    }
    return dp[n - 1][m - 1];
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // 时间复杂度O(N^2)，空间复杂度O(N^2)
        int dp[grid.size()][grid[0].size()];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.size(); ++i) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < grid[0].size(); ++j) dp[0][j] = dp[0][j - 1] + grid[0][j];
        for (int i = 1; i < grid.size(); ++i) {
            for (int j = 1; j < grid[0].size(); ++j) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[grid.size() - 1][grid[0].size() - 1];
    }
};

int maxValue(int** grid, int gridRowLen, int* gridColLen ) {
    // write code here
    
    int m=gridRowLen;
    int n=*gridColLen;
    //对新数组的第一行重新赋值，第一行的最大值只能来自最左边，第一个值是固定不变的
    for (int j=1; j<n; j++) {
        grid[0][j]+=grid[0][j-1];
    }
    //对数组的第一列进行重新赋值，只能来自上方
    for(int i=1;i<m;i++ )
    {
        grid[i][0]+=grid[i-1][0];
    }
    for (int i=1;i<m ; i++) {
        for (int j=1; j<n; j++) {
            //利用三目运算符
            grid[i][j]= grid[i][j-1]>grid[i-1][j]?grid[i][j]+grid[i][j-1]:grid[i][j]+grid[i-1][j];
        }
    
    }
    return grid[m-1][n-1];
}

int maxValue(int** grid, int gridRowLen, int* gridColLen) {
    // 判断输入是否合法
    if (grid == NULL || gridRowLen <= 0 || gridColLen == NULL || *gridColLen <= 0) 
    {
        return 0;
    }
    
    int m = gridRowLen;
    int n = *gridColLen;
    
    // 创建 dp 数组并初始化第一个格子
    int dp[m][n];
    dp[0][0] = grid[0][0];
    
    // 初始化第一行
    for (int j = 1; j < n; j++) 
    {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) 
    {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // 计算其他格子的最大价值
    for (int i = 1; i < m; i++) 
    {
        for (int j = 1; j < n; j++) 
        {
            dp[i][j] = fmax(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    
    // 返回右下角格子的最大价值
    return dp[m-1][n-1];
}
//x++||y++

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        # 动态规划
        m, n = len(grid), len(grid[0])
        # dp[i][j]表示到达(i, j)位置时的最大价值
        dp = [[0] * n for _ in range(m)]
        # 初始化第一行和第一列
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        return dp[-1][-1]

int max_val(int a,int b)
{
    return a>b?a:b;
}
int maxValue(int** grid, int gridRowLen, int* gridColLen ) 
{
    // write code here
    int i=0,col = *gridColLen;
    for(i=gridRowLen-2;i>=0;i--)
        grid[i][col-1] += grid[i+1][col-1];
    for(i=col-2;i>=0;i--)
        grid[gridRowLen-1][i] += grid[gridRowLen-1][i+1];
    for(int i=gridRowLen-2;i>=0;i--)
        for(int j=col-2;j>=0;j--)
            grid[i][j] +=max_val(grid[i+1][j],grid[i][j+1]);
    return grid[0][0];
}

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param grid int整型二维数组 
 * @return int整型
*/
func maxValue( grid [][]int ) int {
    m,n:=len(grid),len(grid[0])
    for i:=1;i<m;i++{
        grid[i][0]+=grid[i-1][0]
    }
    for i:=1;i<n;i++{
        grid[0][i]+=grid[0][i-1]
    }
    for i:=1;i<m;i++{
        for j:=1;j<n;j++{
            grid[i][j]+=max(grid[i-1][j],grid[i][j-1])
        }
    }
    return grid[m-1][n-1]
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

class Solution:
    def maxValue(self , grid: List[List[int]]) -> int:
        # write code here
        # 动态规划
        m, n = len(grid), len(grid[0])
        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1,n + 1):
                dp[i][j] = max(grid[i - 1][j - 1] + dp[i - 1][j], grid[i - 1][j - 1] + dp[i][j - 1])
        return dp[-1][-1]
动态规划，每次走最大路径即可完成

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param grid int整型二维数组
# @return int整型
#
class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        # write code here
        M = len(grid)
        N = len(grid[0])
        dp = [[0]*N for m in range(M)]

    # 记录当前位置的礼物的最大

        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):

            # 初始化第一行，第一列的元素，它不可能从上面，或者左边移动过来，所以说它的大小就是它最大的价值

                if i == 0 and j == 0:
                    print(grid[0][0])
                    dp[i][j] = grid[i][j]

            # 棋盘中非第一行，非第一列中的元素的最大的情况

                elif len(grid) > i > 0 and len(grid[0]) > j > 0:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

                # 棋盘的第一行只能从左移动过去，从上面移动下来不可能

                elif i-1 < 0:
                    print("行列", i, j)
                    dp[i][j] = dp[i][j-1]+grid[i][j]

                # 棋盘的第一列，不可能从左边移动过来，所以只能从上面移动过来
                elif j-1 < 0:
                    dp[i][j] = dp[i-1][j] + grid[i][j]

        return dp[M-1][N-1]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m=grid.size();         //行数m
        int n=grid[0].size();         //列数n
        int rec[m][n];               //记录最大值的二维数组rec，这里空间复杂度高一些
        rec[0][0]=grid[0][0];     //初始化左上角rec
        for(int i=1;i<m;i++){         //填补rec的第一列
            rec[i][0]=rec[i-1][0]+grid[i][0];
        }
        for(int i=1;i<n;i++){        //填补rec的第一行
            rec[0][i]=rec[0][i-1]+grid[0][i];
        }
        for(int i=1;i<m;i++){        //找剩下的rec空的地方的最大值，遍历一遍
            for(int j=1;j<n;j++){
                rec[i][j]=max(rec[i-1][j],rec[i][j-1])+grid[i][j];
            }
        }
        return rec[m-1][n-1];
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        vector<vector<int>>dp(grid.size(),vector<int>(grid[0].size()));//dp[i][j]表示在位置grid[i][j]时的最大价值
        //初始化
        dp[0][0]=grid[0][0];
    for(int i=1;i<grid.size();i++)dp[i][0]=dp[i-1][0]+grid[i][0];
    for(int i=1;i<grid[0].size();i++)dp[0][i]=dp[0][i-1]+grid[0][i];
        for(int i=1;i<grid.size();i++)
        for(int j=1;j<grid[0].size();j++){
            dp[i][j]=max(dp[i][j-1]+grid[i][j],dp[i-1][j]+grid[i][j]);
        }

        return dp[grid.size()-1][grid[0].size()-1];
    }
};