算法的学习笔记—礼物的最大价值
【摘要】 在日常生活中,我们常常需要在有限的资源中找到最优解,这个概念在编程中也经常被应用。今天,我们来探讨一个经典的编程问题:如何在一个充满礼物的棋盘上,从左上角出发,经过多个格子,直到右下角,获取最大的礼物价值。
😀前言
在日常生活中,我们常常需要在有限的资源中找到最优解,这个概念在编程中也经常被应用。今天,我们来探讨一个经典的编程问题:如何在一个充满礼物的棋盘上,从左上角出发,经过多个格子,直到右下角,获取最大的礼物价值。
🥰礼物的最大价值
😊问题描述
假设我们有一个 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),动态规划在这种情况下更加高效和简洁。
动态规划的实现
我们可以通过以下步骤来实现:
- 定义状态:我们定义一个数组
dp
,其中dp[i]
表示到达当前行的第i
列时,能够获取的最大礼物价值。 - 初始化:从左上角开始,初始的礼物价值就是棋盘上的第一个格子的值。
- 状态转移方程:我们需要考虑两种可能的移动方式:
- 从左侧格子移动到当前格子:
dp[i] = dp[i - 1] + value[i]
- 从上方格子移动到当前格子:
dp[i] = dp[i] + value[i]
最终,我们取这两者的最大值,以确保每一步都获得最大可能的礼物价值。
- 从左侧格子移动到当前格子:
- 结果输出:遍历完整个棋盘后,
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)