动态规划2(数塔问题)

2024-01-10 17:38
文章标签 动态 规划 问题 数塔

本文主要是介绍动态规划2(数塔问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

数塔问题是二维情况下动态规划的经典问题,下面以洛谷的一个例题来分析数塔问题以及动态规划:原题链接

题目描述

观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。在这里插入图片描述
在上面的样例中,从7→3→8→7→5 的路径最大

输入格式

第一个行一个正整数 rr ,表示行的数目。后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30

数据范围

对于100%的数据,1 ≤ r ≤ 1000,所有输入在 [0,100] 范围内。

数塔问题递归写法分析:

  • 可以使用一个二维数组存储数塔,需要注意的是,在本题的数塔里,路径可以选择向左或者向右,但是若将数塔存储在二维数组中,数塔路径的选择只能是向下向右下这两个方向
  • 在二维数组中,当前位置的下方是[i + 1][ j ],右下方是[i +1][j + 1]
  • 本题样例中给出的是5层数塔,可以用dfs(1,1)表示从第1行第1列到第5行的最大路径,而想要找到答案,需要先寻找第2行到第5行的最大路径,即将5层数塔的最长路径转化为了4层数塔的最长路径这个子问题。即max{dfs(2,1),dfs(2,2)} + a[1][1]… … 以此类推
  • 当dfs()函数递归到最后1行(x == n)时,如数塔一共5行,目前正在执行dfs(5,1),则直接返回数塔中的第5行第1列的数字a[5][1]即可,之后递归函数会依次向上继续返回

递归写法代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;
int a[N][N];//存储数据
int n;//递归函数中需要设置边界,故将n设为全局变量int dfs(int x,int y)//x表示行,y表示列
{if (x == n) return a[x][y];//递归边界return max(dfs(x + 1,y),dfs(x + 1,y + 1)) + a[x][y];
}int main()
{cin >> n;for (int i = 1;i <= n;i++)//读入数塔:数塔有n行for (int j = 1;j <= i;j++)//每行有n列cin >> a[i][j];cout << dfs(1,1) << endl;//dfs(1,1):从第1行第1列到边界的最大路径return 0;
}

当然,当数据范围很大时,由于递归写法的重叠子问题太多,所以又见到了熟悉的TLE… …话不多说直接上图在这里插入图片描述
下面给出本题的AC代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;
int a[N][N];//存储数塔
int f[N][N];//表示从第i行第j列到第n行的最大路径
int n;int main()
{while (cin >> n){for (int i = 1;i <= n;i++)for (int j = 1;j <= i;j++)cin >> a[i][j];for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始for (int j = 1;j <= i;j++)//每行有i列,且从第一列开始f[i][j] = max(f[i + 1][j],f[i + 1][j + 1]) + a[i][j];//自底向上计算最长路径cout << f[1][1] << endl;//当for循环结束完毕之后f[1][1]:从数塔第1行第1列开始的最长路径}return 0;
}

动态规划的基本思想:将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。我们需要保存已解决的子问题的答案,这样可以避免大量的重复计算,节省时间。我们会用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中,而在需要时再找出已求得的答案。

换个新数塔哈~
在这里插入图片描述

如上图所示,若想找到这个8层数塔的最长路径,即将问题描述为:

  • 从第一行第一列的数字7开始,找出一条最长路径。
    很明显,若想解决上面的问题,有两条路径可以选择:
    从数字7下面的0开始寻找路径(子问题)
    从数字7右下的11开始寻找路径(子问题)

以此类推,不难发现,从红色位置开始找出一条最长路径,这个问题依赖于很多个子问题,而这些子问题构成了绿色部分。

我们只需要计算出①②两个子问题的答案,选择其中较大的值,再加上第一行第一列的那个数字,就可以得到数塔的最长路径。

由以上分析,得出状态转移方程

dp[i][j] = max{dp[i + 1][j],dp[i + 1][j + 1]} + a[i][j]
边界:当i > n时,f[i][j] = 0;

下面再给出数塔的一个例题
原题链接

AC代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;
int a[N][N];//存储数塔
int f[N][N];//表示从第i行第j列到第n行的最大路径
int n;int main()
{int c;cin >> c;while (c--){cin >> n;for (int i = 1;i <= n;i++)for (int j = 1;j <= i;j++)cin >> a[i][j];for (int i = n;i >= 1;i--)//用i来表示行,且从最后一行开始for (int j = 1;j <= i;j++)//每行有i列,且从第一列开始f[i][j] = max(f[i + 1][j],f[i + 1][j + 1]) + a[i][j];//自底向上计算最长路径cout << f[1][1] << endl;//当for循环结束完毕之后f[1][1]:从数塔第一层开始的最长路径}return 0;
}

这篇关于动态规划2(数塔问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/591569

相关文章

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Springboot如何正确使用AOP问题

《Springboot如何正确使用AOP问题》:本文主要介绍Springboot如何正确使用AOP问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录​一、AOP概念二、切点表达式​execution表达式案例三、AOP通知四、springboot中使用AOP导出

Python中Tensorflow无法调用GPU问题的解决方法

《Python中Tensorflow无法调用GPU问题的解决方法》文章详解如何解决TensorFlow在Windows无法识别GPU的问题,需降级至2.10版本,安装匹配CUDA11.2和cuDNN... 当用以下代码查看GPU数量时,gpuspython返回的是一个空列表,说明tensorflow没有找到