一起学习交流~

礼物的最大价值-DP

算法 laomuji 8个月前 (01-21) 322次浏览 已收录 0个评论

目录

题目

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题

状态定义:
创建一个二维数组dp[n][m],表示从dp[0][0]开始到dp[x][y]经过的最大价值

转移方程:

x y dp[x][y] 解释
=0 =0 nums[0][0] 起始位置
>0 =0 nums[x-1][0] 第一列,每个都来依赖上边的一个
=0 >0 nums[0][y-1] 第一行,每个都来依赖左边的一个
>0 >0 max(dp[x-1][y],dp[x][y-1]) +nums[x][y] 其它位置,最大金额为上边或左边的最大金额加上当前金额

代码:

int maxValue(vector<vector<int>> &grid)
{
    if(grid.size()==0||grid[0].size()==0)return 0;
    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 i = 1; i < n; i++)dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int i = 1; i < m; i++)dp[0][i] = dp[0][i-1]+grid[0][i];
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1][m - 1];
}
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论