现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝

每次可以移动到右侧或下侧的相邻位置

到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1：

**输入：**frame = [[1,3,1],[1,5,1],[4,2,1]]
**输出：**12
**解释：**路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

0 < frame.length <= 200

0 < frame[0].length <= 200

动态规划

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

后续不会用到dp[i-1][j]和dp[i][j-1]，所以可以直接在原数组上操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int jewelleryValue(vector<vector<int>> &frame) {
        // dp[i][j] = max(dp[i-1][j]+frame[i][j],dp[i][j-1]+frame[i][j])
        int row = frame.size();
        int col = frame[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i == 0 && j == 0)
                    continue;
                if (i == 0) {
                    frame[i][j] = frame[i][j - 1] + frame[i][j];
                } else if (j == 0) {
                    frame[i][j] = frame[i - 1][j] + frame[i][j];
                } else {
                    frame[i][j] = max(frame[i - 1][j], frame[i][j - 1]) + frame[i][j];
                }
            }
        }
        return frame[row - 1][col - 1];
    }
};