首页 > 编程语言 >算法设计与分析(数字塔问题

算法设计与分析(数字塔问题

时间:2024-09-25 15:53:39浏览次数:9  
标签:数字 int 路径 矩阵 算法 数组 设计 动态



目录

  • 题目——动态规划求解数字塔问题
  • 问题描述
  • 代码实现
  • 输出结果
  • 注意事项
  • 小结:


题目——动态规划求解数字塔问题

在这篇博客中,我们将探讨一个经典的动态规划问题:在一个金字塔形状的数字矩阵中,如何找到从顶部到底部的最大路径和。每次只能向下移动到相邻的数字,最终我们需要计算出这一最大路径和,并输出该路径。

问题描述

给定一个金字塔形状的整数矩阵,其中每个位置的数字代表路径上的点。我们的目标是从顶端开始,找到一条路径,直到达到底部,使得路径上所有数字的总和最大。在移动时,我们只能向下走到下一行的相邻数字。例如,从位置 (i, j) 只能移动到 (i+1, j)(i+1, j+1)

为了求解这个问题,我们可以使用动态规划的方法,通过自下而上的方式逐步计算出每个位置的最大路径和。最后,路径和存储在一个辅助数组中,我们可以通过回溯的方法找出实际的路径。

代码实现

#include <iostream> 
#define N 5 
using namespace std;

int dtower(int a[][N+1], int s[][N+1], int n){
	/*
	a:原矩阵
	s:最优值
	n:矩阵大小 
	*/
	for (int i=1; i<=n; i++) s[n][i] = a[n][i];	// 拷贝最后一行 
	for (int i=n-1; i>0; i--){	// 递推公式 
		for (int j=1; j<=i; j++){
			s[i][j] = a[i][j] + max(s[i+1][j], s[i+1][j+1]);
		}
	}
	return s[1][1];
}

void TraceBack(int a[][N+1], int s[][N+1], int i, int j, int n){
	// 终止条件 
	if (i == n) cout << i << ", " << j << endl;
	// 递归
	else{
		cout << i << ", " << j << endl;
		if (s[i][j] == a[i][j] + s[i+1][j]) TraceBack(a, s, i+1, j, n);	// 选择下方
		else TraceBack(a, s, i+1, j+1, n); 								// 选择下右方
	} 
} 

int main() {
	// 原矩阵
	int a[N+1][N+1] = {  
	    {0, 0, 0, 0, 0, 0},
	    {0, 7, 0, 0, 0, 0},
	    {0, 3, 8, 0, 0, 0},
	    {0, 8, 1, 0, 0, 0},
	    {0, 2, 7, 4, 4, 0},
	    {0, 4, 5, 2, 6, 5}};
    // 最优值矩阵
    int s[N+1][N+1]; 
    
    // 递推求最优值
    cout << dtower(a, s, N) << endl;
    
    // 递归构建最优解
    TraceBack(a, s, 1, 1, N);
}

输出结果

算法设计与分析(数字塔问题_算法

注意事项

数组下标:在使用数组时,请注意下标的范围,避免越界错误。这里我们定义了 N+1 的数组,以简化从 1 开始的索引。

动态规划状态转移:在计算状态转移时,要确保每一步都按照最大值进行更新,以确保路径和的准确性。

路径回溯:回溯时的条件判断要准确,确保能够找到正确的路径。通过判断当前值是否等于来自下方的值,决定路径的选择。

标签:数字,int,路径,矩阵,算法,数组,设计,动态
From: https://blog.51cto.com/u_16672541/12110300

相关文章

  • SSM实验室排课系统 毕业设计源码24944
    摘要随着社会的发展,社会的方方面面都在利用信息化时代的优势。互联网的优势和普及使得各种系统的开发成为必需。本文以实际运用为开发背景,运用软件工程原理和开发方法,它主要是使用动态网页开发技术java作为系统的开发语言,MySQL作为后台数据库。整个开发过程首先对实验室排......
  • 工地扬尘自动监测识别算法、扬尘检测算法、扬尘检测算法样本标注
    在现代城市的发展过程中,环境问题日益凸显,尤其是空气质量问题。其中,扬尘作为影响空气质量的重要因素之一,其治理和监测显得尤为重要。一、应用场景1.环境保护-空气质量监测:在城市主要道路、工业园区等区域安装扬尘检测系统,实时监测空气质量,及时采取措施减少污染。-生态恢复:在生......
  • 2024 年面向算法交易者的十大开源 Python 库
    作者:老余捞鱼原创不易,转载请标明出处及原作者。写在前面的话:    本文介绍2024年面向算法交易者/量化交易者/数据驱动交易者的十大Python库,文中详细描述了每个库优缺点、用途和特点,同时提供了外部链接供用户进一步学习。​​​​​​​    如果您对......
  • 投票算法 Boyer-Moore
    投票算法Boyer-Moore算法描述Boyer-Moore投票算法是一种用来在线性时间内找到数组中出现次数超过一半(即多数元素)的算法。这个算法非常高效,因为它只需要一次遍历数组,并且使用常数级别的额外空间。leetcode169题:多数元素算法思路维护一个候选元素和一个计数器来实现投票算......
  • 架构师日记-从数据库发展历程到数据结构设计探析
    一数据库发展史起初,数据的管理方式是文件系统,数据存储在文件中,数据管理和维护都由程序员完成。后来发展出树形结构和网状结构的数据库,但都存在着难以扩展和维护的问题。直到七十年代,关系数据库理论的提出,以表格形式组织数据,数据之间存在关联关系,具有了良好的结构化和规范......
  • 基于单片机设计的自动门控制系统
    一、前言自动门控制系统是一种智能化的应用,能够根据人体接近信号自动完成门的打开和关闭操作。在传统的门控系统中,通常需要人手动进行门的开启和关闭,不仅费时费力,还不够智能高效。本项目采用了STC89C52作为主控芯片,并结合红外热释电模块和28BYJ-48步进电机,实现了门的自动打开和关闭......
  • 基于python+flask框架的临海市社区居民户籍管理系统的设计与实现(开题+程序+论文) 计算
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着城市化进程的加速,临海市作为一座快速发展的城市,其社区管理面临着前所未有的挑战。社区居民数量的激增、户籍信息的复杂化以及人口流动......
  • 基于python+flask框架的零食销售系统的设计与实现(开题+程序+论文) 计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着互联网的飞速发展,电子商务已成为现代商业活动的重要组成部分,深刻改变了人们的消费习惯。零食作为日常生活中不可或缺的一部分,其市场需......
  • 基于python+flask框架的流浪动物救助系统的设计与实现(开题+程序+论文) 计算机毕设
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容研究背景随着城市化进程的加快和生活方式的改变,流浪动物问题日益凸显,成为社会关注的焦点之一。城市中流浪猫狗数量的激增,不仅给城市环境带来压力,也......
  • 时序预测 | Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数
    时序预测|Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数据(单输入单输出)目录时序预测|Matlab实现SSA-TCN麻雀搜索算法优化时间卷积网络时序预测-递归预测未来数据(单输入单输出)预测效果基本介绍程序设计参考资料预测效果基本介绍1.Matlab实现SSA-TCN......