😀前言
在日常生活中，我们常常需要在有限的资源中找到最优解，这个概念在编程中也经常被应用。今天，我们来探讨一个经典的编程问题：如何在一个充满礼物的棋盘上，从左上角出发，经过多个格子，直到右下角，获取最大的礼物价值。

🥰礼物的最大价值

NowCoder

😊问题描述

假设我们有一个 m \* n 的棋盘，每个格子上放有一个礼物，每个礼物都有其对应的价值（大于 0）。我们从棋盘的左上角出发，每次只能向右或向下移动一格，最终到达右下角。目标是通过这样的移动路径，获取尽可能多的礼物价值。

示例

假设棋盘如下所示：

1    10   3    8
12   2    9    6
5    7    4    11
3    7    16   5

在这个棋盘上，我们可以得到最大礼物价值的路径是：

1 + 12 + 5 + 7 + 7 + 16 + 5 = 53

😀解题思路

要解决这个问题，我们可以采用动态规划的策略。动态规划是一种优化技术，适用于将复杂问题分解成更小的子问题并逐步解决的场景。相比于深度优先搜索（DFS），动态规划在这种情况下更加高效和简洁。

动态规划的实现

我们可以通过以下步骤来实现：

1. 定义状态：我们定义一个数组 dp，其中 dp[i] 表示到达当前行的第 i 列时，能够获取的最大礼物价值。
2. 初始化：从左上角开始，初始的礼物价值就是棋盘上的第一个格子的值。
3. 状态转移方程：我们需要考虑两种可能的移动方式：
   • 从左侧格子移动到当前格子：dp[i] = dp[i - 1] + value[i]
   • 从上方格子移动到当前格子：dp[i] = dp[i] + value[i] 最终，我们取这两者的最大值，以确保每一步都获得最大可能的礼物价值。
4. 结果输出：遍历完整个棋盘后，dp[n-1]（n为棋盘的列数）即为我们所需的最大礼物价值。

😃代码实现

以下是具体的代码实现：

应该用动态规划求解，而不是深度优先搜索，深度优先搜索过于复杂，不是最优解。

public int getMost(int[][] values) {
    // 检查输入是否合法
    if (values == null || values.length == 0 || values[0].length == 0) {
        return 0;
    }

    int n = values[0].length;  // 获取棋盘的列数
    int[] dp = new int[n];     // 初始化dp数组

    // 遍历棋盘的每一行
    for (int[] value : values) {
        dp[0] += value[0];  // 更新当前行的第一个格子的值
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];  // 更新当前行其他格子的值
        }
    }
    
    // 返回右下角的最大礼物价值
    return dp[n - 1];
}

代码解析

• 初始化部分：我们首先检查输入是否为空，避免不合法的输入导致程序错误。然后，初始化 dp 数组，dp[i] 记录到达当前行第 i 列的最大礼物价值。
• 动态规划求解：我们遍历每一行，对于每一个格子，计算其从上方或左侧格子到达的最大可能礼物价值，并更新 dp 数组。
• 时间复杂度：该算法的时间复杂度为 O(m * n)，其中 m 和 n 分别为棋盘的行数和列数。这种复杂度保证了算法在处理大规模数据时的高效性。

😄总结

通过动态规划，我们成功地解决了在棋盘中获取最大礼物价值的问题。动态规划的核心在于将问题拆解成一系列可以递推的小问题，从而避免了重复计算，极大地提高了计算效率。在这个问题中，动态规划帮助我们在短时间内找到了最优路径，从而获取了最大的礼物价值。希望通过这个例子的讲解，能让你对动态规划有更深的理解，并能将其应用到更多类似的问题中。