leetcode LCR 166.珠宝的最高价值

本文主要是介绍leetcode LCR 166.珠宝的最高价值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：dp

这里其实很简单，就是一个网格图，两个固定状态，一个向下，一个向右。

其实状态方程就已经出来了，就是dp[i][j]=max(dp[i-1][j],dp[i][j-1])+value。

注意：在最上面一行或者最左边一列的时候，其实就一种状态，在最上面一行的时候只有向右走的状态，在最左边一列时只有向下走的状态，所以需要额外处理一下。

上代码：

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

这篇关于leetcode LCR 166.珠宝的最高价值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---