数塔问题(蛮力算法和动态规划)
题目:如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大,及路径情况。(使用蛮力算法和动态规划算法分别实现)

#include<bits/stdc++.h>
#define MAX_SIZE 100
using namespace std;
//蛮力算法
int maxPathSumForce(int pyramid[][MAX_SIZE],int row){if(row==1){return pyramid[0][0];}int maxSum=pyramid[0][0];for(int i=1;i<row;i++){for(int j=0;j<i;j++){if(j==0){pyramid[i][j]+=pyramid[i-1][j]; }else if(j==i){pyramid[i][j]+=pyramid[i-1][j-1];}else{pyramid[i][j] += (pyramid[i - 1][j - 1] > pyramid[i - 1][j] ? pyramid[i - 1][j - 1] : pyramid[i - 1][j]);}if (pyramid[i][j] > maxSum) {maxSum = pyramid[i][j];}
}}return maxSum;
} //动态规划算法int maxPathSumDP(int pyramid[][MAX_SIZE], int rows) {if (rows == 1) {return pyramid[0][0];}for (int i = rows - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {pyramid[i][j] += (pyramid[i + 1][j] > pyramid[i + 1][j + 1] ? pyramid[i + 1][j] : pyramid[i + 1][j + 1]);}}return pyramid[0][0];
}signed main()
{int pyramid[MAX_SIZE][MAX_SIZE];int row,num;cout<<"请输入数塔的层数:";cin>>row;cout<<"请输入数塔的数字(每层从左到右依次输入):"<<endl;for(int i=0;i<row;i++){for(int j=0;j<=i;j++){cin>>num;pyramid[i][j]=num;}}cout<<"蛮力算法最大路径和为:"<<maxPathSumForce(pyramid,row)<<endl;cout<<"动态规划算法最大路径和为:"<<maxPathSumDP(pyramid,row)<<endl; }
蛮力算法的解释:
1. 首先,如果金字塔只有一行(rows == 1),则直接返回金字塔顶部的值(pyramid[0][0])。
2. 初始化最大路径和为金字塔顶部的值(maxSum = pyramid[0][0])。
3. 使用两个嵌套的循环遍历金字塔的每一行和每一列。外层循环变量i表示行数,内层循环变量j表示列数。
4. 在内层循环中,根据当前位置的行数和列数,计算当前位置的值。具体计算方式如下:
- 如果当前位置是行的开头(j == 0),则当前位置的值等于上一行同列位置的值加上当前位置的值(pyramid[i][j] += pyramid[i - 1][j])。
- 如果当前位置是行的末尾(j == i),则当前位置的值等于上一行前一列位置的值加上当前位置的值(pyramid[i][j] += pyramid[i - 1][j - 1])。
- 否则,当前位置的值等于上一行前一列位置的值和上一行同列位置的值中的较大值(pyramid[i][j] += (pyramid[i - 1][j - 1] > pyramid[i - 1][j] ? pyramid[i - 1][j - 1] : pyramid[i - 1][j]))。
5. 在内层循环中,每次更新当前位置的值后,判断当前位置的值是否大于最大路径和(maxSum)。如果是,则更新最大路径和为当前位置的值。
动态规划算法的解释:(从下到上代码更加简洁,可能性更小)
1. 首先,如果金字塔只有一行(rows == 1),则直接返回金字塔顶部的值(pyramid[0][0])。
2. 使用两个嵌套的循环从倒数第二行开始向上遍历金字塔的每一行和每一列。外层循环变量i表示行数,内层循环变量j表示列数。
3. 在内层循环中,根据当前位置的行数和列数,计算当前位置的值。具体计算方式如下:
- 当前位置的值等于当前位置的值加上 下一行同列位置和下一行下一列位置中的较大值(pyramid[i][j] += (pyramid[i + 1][j] > pyramid[i + 1][j + 1] ? pyramid[i + 1][j] : pyramid[i + 1][j + 1]))。
4. 循环结束后,金字塔顶部的值即为从顶部到底部的最大路径和。
5. 返回金字塔顶部的值。
相关文章:
数塔问题(蛮力算法和动态规划)
题目:如下图是一个数塔,从顶部出发在每一个节点可以选择向左或者向右走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大,及路径情况。(使用蛮力算法和动态规划算法分别实现) #include…...
启动 Redis 服务和连接到 Redis 服务器
启动 Redis 服务和连接到 Redis 服务器的步骤通常依赖于你的操作系统和 Redis 的安装方式。以下是一些常见的步骤: ### 启动 Redis 服务 对于大多数 Linux 发行版,Redis 服务可以通过以下命令启动: 1. 如果 Redis 是通过包管理器安装的&am…...
我独自升级崛起在哪下载 我独自升级电脑PC端下载教程分享
将于5月8日在全球舞台闪亮登场的动作角色扮演游戏《我独自升级崛起》,灵感源自同名热门动画与网络漫画,承诺为充满激情的游戏玩家群体带来一场集深度探索与广阔体验于一身的奇幻旅程。该游戏以独特的网络武侠世界观为基底,展现了一位普通人踏…...
STM32F4xx开发学习—GPIO
GPIO 学习使用STM32F407VET6GPIO外设 寄存器和标准外设库 1. 寄存器 存储器映射 存储器本身是不具有地址的,是一块具有特定功能的内存单元,它的地址是由芯片厂商或用户分配,给存储器分配地址的过程就叫做存储区映射。给内存单元分配地址之后…...
引领农业新质生产力,鸿道(Intewell®)操作系统助力农业机器人创新发展
4月27日至29日,2024耒耜国际会议在江苏大学召开。科东软件作为特邀嘉宾出席此次盛会,并为江苏大学-科东软件“农业机器人操作系统”联合实验室揭牌。 校企联合实验室揭牌 在开幕式上,江苏大学、科东软件、上交碳中和动力研究院、遨博智能研究…...
扩展学习|一文读懂知识图谱
一、知识图谱的技术实现流程及相关应用 文献来源:曹倩,赵一鸣.知识图谱的技术实现流程及相关应用[J].情报理论与实践,2015, 38(12):127-132. (一)知识图谱的特征及功能 知识图谱是为了适应新的网络信息环境而产生的一种语义知识组织和服务的方…...
ubuntu中的docker记录(3)——如何安装nvidia-docker以更好地支持GPU加速计算应用程序的运行
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、nvidia-docker2的安装1. 安装docker2. 安装nvidia-docker2(1) 添加密钥(2) 更新软件列表(3) 安装nvidia-docker2(4) 测试nvidia-docker2 二、可能的报错及解…...
MLP实现fashion_mnist数据集分类(1)-模型构建、训练、保存与加载(tensorflow)
1、查看tensorflow版本 import tensorflow as tfprint(Tensorflow Version:{}.format(tf.__version__)) print(tf.config.list_physical_devices())2、fashion_mnist数据集下载与展示 (train_image,train_label),(test_image,test_label) tf.keras.datasets.fashion_mnist.l…...
ChatGPT-税收支持新质生产力
Prompt: 税收发展助力新质生产力 Response: 是的,税收发展可以促进新质生产力的发展。通过税收政策的调整和优化,政府可以提供更好的创新环境,激发企业投资研发,推动新技术、新产品的出现,从而推动经济结构升级和新…...
Linux下深度学习虚拟环境的搭建与模型训练
在深度学习实践中,环境配置是十分重要且免不了的一步。本文以 YOLOv4 模型,介绍在Linux下虚拟环境配置到模型训练的过程。 安装Miniconda: Miniconda是Anaconda的一个轻量级版本,非常适合用于科学计算和数据处理。 wget https:…...
Map-Reduce是个什么东东?
MapReduce是一种用于使用并行分布式算法在集群计算机上处理大型数据集的编程模型及其相关实现。这一概念首先由Google普及,并随后作为Apache Hadoop项目的一部分开源发布。 MapReduce的基本工作流程: 映射(Mapping):这是第一阶段,…...
上位机工作感想-从C#到Qt的转变-2
2.技术总结 语言方面 最大收获就是掌握了C Qt编程,自己也是粗看了一遍《深入理解计算机系统》,大致了解了计算机基本组成、虚拟内存、缓存命中率等基基础知识,那本书确实有的部分看起来很吃力,等这段时间忙完再研读一遍。对于封装…...
【C++】C++ 中 的 lambda 表达式(匿名函数)
C11 引入的匿名函数,通常被称为 Lambda 函数,是语言的一个重要增强,它允许程序员在运行时创建简洁的、一次性使用的函数对象。Lambda 函数的主要特点是它们没有名称,但可以捕获周围作用域中的变量,这使得它们非常适合在…...
OpenSSL实现AES-CBC加解密,可一次性加解密任意长度的明文字符串或字节流(QT C++环境)
本篇博文讲述如何在Qt C的环境中使用OpenSSL实现AES-CBC-Pkcs7加/解密,可以一次性加解密一个任意长度的明文字符串或者字节流,但不适合分段读取加解密的(例如,一个4GB的大型文件需要加解密,要分段读取,每次…...
cURL:命令行下的网络工具
序言 在当今互联网时代,我们经常需要与远程服务器通信,获取数据、发送请求或下载文件。在这些情况下,cURL 是一个强大而灵活的工具,它允许我们通过命令行进行各种类型的网络交互。本文将深入探讨 cURL 的基本用法以及一些高级功能…...
Baumer工业相机堡盟工业相机如何通过NEOAPISDK查询和轮询相机设备事件函数(C#)
Baumer工业相机堡盟工业相机如何通过NEOAPISDK查询和轮询相机设备事件函数(C#) Baumer工业相机Baumer工业相机NEOAPI SDK和相机设备事件的技术背景Baumer工业相机通过NEOAPISDK在相机中查询和轮询相机设备事件函数功能1.引用合适的类文件2.通过NEOAPISDK…...
Day45代码随想录动态规划part07:70. 爬楼梯(进阶版)、322. 零钱兑换、279.完全平方数、139.单词拆分
Day45 动态规划part07 完全背包 70. 爬楼梯(进阶版) 卡码网链接:57. 爬楼梯(第八期模拟笔试) (kamacoder.com) 题意:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 < m < n)个…...
土壤重金属含量分布、Cd镉含量、Cr、Pb、Cu、Zn、As和Hg、土壤采样点、土壤类型分布
土壤是人类赖以生存和发展的重要资源之一,也是陆地生态系统重要的组成部分。近年来, 随着我国城市化进程加快,矿产资源开发、金属加工冶炼、化工生产、污水灌溉以及不合理的化肥农药施用等因素导致重金属在农田土壤中不断富集。重金属作为土壤环境中一种具有潜在危害…...
力扣:100284. 有效单词(Java)
目录 题目描述:输入:输出:代码实现: 题目描述: 有效单词 需要满足以下几个条件: 至少 包含 3 个字符。 由数字 0-9 和英文大小写字母组成。(不必包含所有这类字符。) 至少 包含一个 …...
如何快速掌握DDT数据驱动测试?
前言 网盗概念相同的测试脚本使用不同的测试数据来执行,测试数据和测试行为完全分离, 这样的测试脚本设计模式称为数据驱动。(网盗结束)当我们测试某个网站的登录功能时,我们往往会使用不同的用户名和密码来验证登录模块对系统的影响&#x…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
CMake基础:构建流程详解
目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
