剑指offer47_new：珠宝的最高价值

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

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
答案：

Python

class Solution:
    def jewelleryValue(self, frame: List[List[int]]) -> int:
        if len(frame) == 0 or len(frame[0]) == 0:
            return 0
        m, n = len(frame), len(frame[0])
        dp = [[0]* n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = frame[i][j]
                elif i == 0:
                    dp[i][j] = dp[i][j-1] + frame[i][j]
                elif j == 0:
                    dp[i][j] = dp[i-1][j] + frame[i][j]
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + frame[i][j]
        
        return dp[-1][-1]

Java

// 版本1
class Solution {
    public int jewelleryValue(int[][] frame) {
        int[][] dp = new int[frame.length][frame[0].length];
        int left = 0, up = 0;
        for (int i = 0; i < frame.length; ++i) {
            for (int j = 0; j < frame[0].length; ++j) {
                up = i > 0 ? dp[i - 1][j] : 0;
                left = j > 0 ? dp[i][j - 1] : 0;
                dp[i][j] = frame[i][j] + Math.max(up, left);
            }
        }

        return dp[frame.length - 1][frame[0].length - 1];
    }
}

// 版本2
class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        int dp[][] = new int[m][n];
        dp[0][0] = frame[0][0];
        for (int i = 1; i < m; ++i) {
            dp[i][0] = frame[i][0] + dp[i - 1][0];
        }
        for (int j = 1; j < n; ++j) {
            dp[0][j] = frame[0][j] + dp[0][j - 1];
        }

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}