当前位置: 首页> 汽车> 报价 > 动态规划数字三角形模型——AcWing 1015. 摘花生

动态规划数字三角形模型——AcWing 1015. 摘花生

时间:2025/7/12 6:57:35来源:https://blog.csdn.net/u014114223/article/details/139887020 浏览次数: 0次

动态规划数字三角形模型

定义

动态规划数字三角形模型是在一个三角形的数阵中,通过一定规则找到从顶部到底部的最优路径或最优值。

运用情况

通常用于解决具有递推关系、需要在不同路径中做出选择以达到最优结果的问题。比如计算最短路径、最大和等

注意事项

  • 正确定义状态表示,确保能涵盖所有可能情况且无冗余。
  • 注意边界条件的处理。
  • 确保递推关系的正确性和完整性。

解题思路

  • 确定状态:一般是用一个二维数组来表示在某个位置时的最优值。
  • 建立递推关系:根据问题的具体要求,找到从上层到下层每个位置的最优值与之前位置的关系。
  • 从顶部开始逐步计算,根据递推关系更新状态,最终得到底部的最优解。

例如,在一个数字三角形中,要求从顶部到底部路径上数字之和最大。则状态可以定义为 dp[i][j]表示到达第 i 行第 j 列位置时的最大和,递推关系可能是 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。通过从顶部向下依次计算状态,最终得到底部的最大和。

AcWing 1015. 摘花生

题目描述

1015. 摘花生 - AcWing题库

运行代码

#include <iostream>
#include <cstring>
using namespace std;
int dp[101][101];
int main() {int T;cin >> T;while (T--) {int R, C;cin >> R >> C;for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {cin >> dp[i][j];}}for (int i = 1; i <= R; i++) {for (int j = 1; j <= C; j++) {dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);}}cout << dp[R][C] << endl;}return 0;
}

代码思路

  • 定义一个二维数组 dp[101][101] 来存储在每个位置能获得的最大花生数。
  • 对于输入的每组数据,先读取花生苗的行数 R 和列数 C,以及每行每列花生苗上的花生数量并存储到数组中。
  • 然后通过两个嵌套的循环遍历整个花生地。在每个位置 (i, j) ,通过比较从上方 (i - 1, j) 位置过来的最大花生数和从左方 (i, j - 1) 位置过来的最大花生数,取较大值加上当前位置的花生数,更新该位置的 dp[i][j] ,这就体现了动态规划的思想,即每个位置的最优值是基于之前已计算位置的最优值得到的。
  • 当遍历完整个花生地后,最后一行最后一列的 dp[R][C] 就是从西北角到东南角能摘到的最多花生数,输出即可。

改进思路

  1. 空间优化:可以观察到在计算过程中,实际上只需要当前行和上一行的信息,所以可以通过滚动数组的方式来减少空间复杂度,只使用两行的空间来进行计算。
  2. 输入优化:可以考虑对输入数据的读取进行一些优化,比如使用更快的输入流或采用更高效的输入处理方式。
  3. 异常处理:可以添加一些对输入数据合法性的检查和异常处理机制,以应对可能出现的不合法输入情况。

其它代码

#include <iostream>
#include <cstring>
using namespace std;
void run()
{int a[110][110], f[110][110];memset(a, 0, sizeof a);memset(f, 0, sizeof f);int r, c;cin >> r >> c;for(int i = 1; i <= r; i ++)for(int j = 1; j <= c; j ++)cin >> a[i][j];for(int i = 1; i <= r; i ++)for(int j = 1; j <= c; j ++)f[i][j] = max(f[i][j - 1], f[i - 1][j]) + a[i][j];cout << f[r][c] << endl;
}
int main()
{int t;cin >> t;while(t--) run();return 0;
}

代码思路

  • run 函数中:
    • 定义了两个二维数组 a 用于存储花生地中每个位置的花生数量,f 用于存储到达每个位置的最大花生数。
    • 通过 memset 对两个数组进行初始化清零。
    • 读取花生地的行数 r 和列数 c,并输入每个位置的花生数量到 a 中。
    • 然后通过两层循环,在每个位置 (i, j) ,通过比较从左边 (i, j - 1) 和上边 (i - 1, j) 过来的最大花生数,取较大值加上当前位置的花生数,更新 f[i][j],这体现了动态规划的递推过程。最后输出右下角 f[r][c] 的值,即从西北角到东南角能获取的最大花生数。
  • 在 main 函数中,读取测试用例的数量 t,然后逐个调用 run 函数进行处理。
关键字:动态规划数字三角形模型——AcWing 1015. 摘花生

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: