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

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

用时：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];
    }
};