一、題目解析

frame二維矩陣中每個值代表珠寶的價值，現在從左上角開始拿珠寶，只能向右或向下拿珠寶，到達右下角時停止拿珠寶，要求拿的珠寶價值最大。

二、算法解析

1.狀態表示

我們想要知道的是到達[i,j]為位置時的最大價值，所以dp[i][j]表示：到達[i,j]位置時，珠寶的最大價值

2.狀態轉移方程

依舊根據最近一步劃分問題

3.初始化

初始化要確保(1)初始化的值保證后面填表正確(2) 下標的映射關系

觀察左邊的圖，我們能發現帶有小圓圈的格子在填表時會發生越界操作，所以只需要加一行加一列即可。都初始化為0 則是保證填值正確，對于小圓圈dp[1][1]的最大價值為i它本身的價值，所以dp[i-1][j]和dp[i][j-1]初始化為0，其他同理，

此時下標的映射關系為dp[i][i]~fraem[i-1][j-1]

4.填表順序

從左到右，從上到下

5.返回值

返回到達右下角的最大價值，即dp[i][j]

可以動手去自己實現一下，鏈接：LCR 166. 珠寶的最高價值 - 力扣（LeetCode）

三、代碼示例

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

?

看到最后，如果對您有所幫助，還請點贊、收藏、關注，點點關注不迷路，我們下期再見！?