LCR166. 珠宝的最高价值

题目描述：

现有一个记作二维矩阵 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

---

解题分析及思路：

对应动态规划解法：

1. 定义状态： 在这个问题中，状态可以定义为到达每个位置时的最大珠宝总价值。我们可以使用二维数组 frame 来表示状态，其中 frame[i][j] 表示到达位置 (i, j) 时的最大珠宝总价值，所以在整个过程中都是在原数组上进行修改。

2. 找到状态转移方程： 我们从左上角开始遍历二维矩阵，对于每个位置 (i, j)，我们有两个选择：要么是从上方 (i-1, j) 移动过来，要么是从左方 (i, j-1) 移动过来。因此，状态转移方程可以表示为：

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

   这表示到达当前位置的最大珠宝总价值等于当前位置珠宝的价值加上从上方或左方移动过来的最大珠宝总价值。

3. 初始化： 无需进行额外初始化

4. 递推求解： 通过嵌套循环遍历二维矩阵，根据状态转移方程计算每个位置的最大珠宝总价值。

5. 计算最终结果： 最终的结果即为到达右下角位置 (len(frame)-1, len(frame[0])-1) 时的最大珠宝总价值。

注意⚠️：唯一需要注意的是，当横坐标或者纵坐标为0时，此处frame[i][j]可能没有上方元素或左方元素，此时需要额外处理。

func jewelleryValue(frame [][]int) int {
	max := func(i, j int) int {
		if i > j {
			return i
		}
		return j
	}
	for indexI := range frame {
		for indexJ := range frame[indexI] {
			if indexI == 0 && indexJ == 0 {
				continue
			}
			if indexI == 0 {
				frame[indexI][indexJ] = frame[indexI][indexJ] + frame[indexI][indexJ-1]
				continue
			}
			if indexJ == 0 {
				frame[indexI][indexJ] = frame[indexI][indexJ] + frame[indexI-1][indexJ]
				continue
			}
			frame[indexI][indexJ] = frame[indexI][indexJ] + max(frame[indexI-1][indexJ], frame[indexI][indexJ-1])
		}
	}
	return frame[len(frame)-1][len(frame[0])-1]
}

复杂度：

• 时间复杂度：O(MN)，M,N 分别为矩阵行高、列宽；动态规划需遍历整个 frame 矩阵，使用 O(MN) 时间。
• 空间复杂度：O(1)，原地修改使用常数大小的额外空间。

执行结果：

• 执行耗时:5 ms,击败了43.14% 的Go用户
• 内存消耗:3.3 MB,击败了96.08% 的Go用户