数据结构学习 jz47礼物的最大价值

2024-01-03 16:34:22

关键词:动态规划 滚动数组

用时:17min

题目:

?思路:

dp状态:

dp[i][j]取到第i行第j列的珠宝时的最大价值。

因为只和它的左边和上边的状态相关,所以可以变成一个滚动数组,滚动数组存每一行的dp状态。

遍历顺序:一行一行遍历,遍历结果存dp。

?转移方程:

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

复杂度计算:

时间复杂度O(nm)

空间复杂度O(n)

代码:

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        
        vector<int> dp(frame[0].size());
        for(int i=0;i<frame.size();++i)
        {
            for(int j=0;j<frame[0].size();++j)
            {
                int max=frame[i][j];
                if(i>0)
                    max=std::max(max,frame[i][j]+dp[j]);
                if(j>0)
                    max=std::max(max,frame[i][j]+dp[j-1]);
                dp[j]=max;
            }
        }
        return dp[frame[0].size()-1];
    }
};

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