LeetCode 剑指 Offer 47. 礼物的最大价值

Categories:

题目描述
思路分析
1. 解法一：二维 DP（推荐）
相似题目

题目描述

✅ 剑指 Offer 47. 礼物的最大价值

思路分析

解法一：二维 DP（推荐）

核心思路：

只能向右或向下移动，典型的网格路径最大和问题。

dp[i][j] 表示到达 (i,j) 的最大价值。

状态转移为 grid[i][j] + max(dp[i-1][j], dp[i][j-1])。

复杂度分析：

时间复杂度：O(m * n)，其中 m、n 表示网格尺寸。

空间复杂度：O(n)，使用一维滚动数组。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int left = j > 0 ? dp[j - 1] : 0;
                int up = dp[j];
                dp[j] = Math.max(left, up) + grid[i][j];
            }
        }

        return dp[n - 1];
    }
}

func maxValue(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	dp := make([]int, n)

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			left := 0
			if j > 0 {
				left = dp[j-1]
			}
			up := dp[j]
			if left > up {
				dp[j] = left + grid[i][j]
			} else {
				dp[j] = up + grid[i][j]
			}
		}
	}

	return dp[n-1]
}

相似题目

题目	难度	考察点
62. 不同路径	中等	动态规划
64. 最小路径和	中等	动态规划
120. 三角形最小路径和	中等	动态规划
931. 下降路径最小和	中等	动态规划
70. 爬楼梯	简单	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/87069403