算法的学习笔记—礼物的最大价值

举报
尘觉 发表于 2024/08/31 17:46:09 2024/08/31
【摘要】 在日常生活中,我们常常需要在有限的资源中找到最优解,这个概念在编程中也经常被应用。今天,我们来探讨一个经典的编程问题:如何在一个充满礼物的棋盘上,从左上角出发,经过多个格子,直到右下角,获取最大的礼物价值。

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

🥰礼物的最大价值

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 分别为棋盘的行数和列数。这种复杂度保证了算法在处理大规模数据时的高效性。

😄总结

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。