47.礼物的最大价值

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 47. 礼物的最大价值-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

个人尝试❌

局部最优解 ≠ 全局最优

class Solution {
    public int jewelleryValue(int[][] frame) {
        if (frame.length == 0 && frame[0].length == 0) return 0;

        int i = frame.length - 1;
        int j = frame[0].length - 1;
        
        int[] dp = new int[j + 1];
        dp[j] = frame[i][j];
        
        while (i > 0 || j > 0) {      
            if (i == 0 || (j >= 1 && i >= 1 && frame[i][j - 1] >= frame[i - 1][j])){
                dp[j - 1] = dp[j] + frame[i][j - 1];
                j--;
            } else if (j == 0 || (j >= 1 && i >= 1 && frame[i][j - 1] < frame[i - 1][j])) {
                dp[j] = dp[j] + frame[i - 1][j];
                i--;
            }
        }
        
        return dp[0];
    }
}

frame = [
[1,4,8,6,2,2,1,7],
[4,7,3,1,4,5,5,1],
[8,8,2,1,1,8,0,1],
[8,9,2,9,8,0,8,9],
[5,7,5,7,1,8,5,5],
[7,0,9,4,5,6,5,6],
[4,9,9,7,9,1,9,0]
]

程序输出：78❌
预期结果：86

优秀题解

还得老老实实一行一行遍历寻求“踏实”的最优解

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length, n = frame[0].length;
        for(int j = 1; j < n; j++) // 初始化第一行
            frame[0][j] += frame[0][j - 1];
        for(int i = 1; i < m; i++) // 初始化第一列
            frame[i][0] += frame[i - 1][0];
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                frame[i][j] += Math.max(frame[i][j - 1], frame[i - 1][j]);
        return frame[m - 1][n - 1];
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/solutions/181512/mian-shi-ti-47-li-wu-de-zui-da-jie-zhi-dong-tai-gu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。