【动态规划】07路径问题_礼物的最大价值_C++(medium)

发布时间:2023年12月18日

题目链接:leetcode礼物的最大价值


目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求怎样走才能可以拿到最高价值的珠宝

由题可得:

  • 只能从架子的左上角开始拿珠宝
  • 每次可以移动到右侧或下侧的相邻位置
  • 到达珠宝架子的右下角时,停止拿取

我们用示例一来分析:

当我们沿着这条路径走的时候可以得到最大值:12


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

dp[i]表示到达i拿到最高价值的珠宝

这种状态表示怎么来的?

1.经验+题目要求

用之前或者之后的状态,推导出dp[i][j]的值;

根据最近的最近的一步,来划分问题

经验:以i位置为结尾

题目让我们求到达右下角拿到最高价值的珠宝,那么这里我们可以dp[i][j]来表示。

所以这里我们用i*j表示右下角位置;

2.状态转移方程

dp[i][j]等于什么?

因为我们只能每次可以移动到右侧或下侧的相邻位置

所以到达i位置有两种情况:

第一种:从[i-1][j]到达i位置

我们这里只要知道到达[i-1][j]拿到最高价值的珠宝,再加上[i]位置的珠宝价值(cost[i][j])

就可以得到i位置拿到最高价值的珠宝(dp[i][j]);

而“到达[i-1][j]拿到最高价值的珠宝”正好是我们的状态表示:dp[i-1][j]

第二种:从[i][j-1]到达i位置

我们这里只要知道到达[i][j-1]拿到最高价值的珠宝,再加上[i]位置的珠宝价值(cost[i][j])

就可以得到i位置拿到最高价值的珠宝(dp[i][j]);

而“到达[i][j-1]拿到最高价值的珠宝”正好是我们的状态表示:dp[i][j-1]

总结这两种情况:

因为题目让我们求的是拿到最高价值的珠宝

所以这里我们要取这两种情况的最大值

dp[i][j]=max(dp[i-1][j]+dp[i][j-1])+cost[i][j]

3.初始化

(保证填表的时候不越界)

由我们的状态转移方程得:

在0行0列的时候越界,所以我们这里可以在m*n的外围多加1行1列,如图:

还有一个问题是:

我们要拿新增用来初始化的行和列要初始化为几呢?

这里我们需要注意的一点就是在dp[1][1]的时候,最大的珠宝价值就是他本身cost

所以我们只要在dp表里的dp[0][1]、dp[1][0]中任选一个

初始化为cost[0][0]就可以了

我们这里选择[0][1]初始化为cost[0][0]

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:到达该位置的上面和左边位置的方式

所以填表顺序:

从上到下填写每一行

从左到右填写每一列

5.返回值

(根据题目要求和状态表示)

综上分析:

返回值为:dp[m][n];


编写代码:

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
    //1.创建dp表
    //2.初始化
    //3.填表
    //4.返回结果

    int n=frame.size();
    int m=frame[0].size();
    vector<vector<int>> dp(n+1,vector<int>(m+1));
    for(int i=1;i<n+1;i++)
        for(int j=1;j<m+1;j++)
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
    return dp[n][m];
    }
};

文章来源:https://blog.csdn.net/lsj1345714539566/article/details/135007026
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。