当前位置：首页 > news >正文

穿越数据森林与网络迷宫：树与图上动态规划实战指南

news 来源：原创 2025/7/17 11:33:46

在 C++ 算法的浩瀚宇宙中，树与图就像是神秘的迷宫和茂密的森林，充满了未知与挑战。而动态规划则是我们探索其中的神奇罗盘，帮助我们找到最优路径。今天，就让我们一起深入这片神秘领域，揭开树与图上动态规划的神秘面纱！

树与图上动态规划的独特魅力

与线性动态规划相比，树与图上的动态规划更加复杂，因为它们的结构不再是简单的线性，而是具有分支和循环。但正是这种复杂性，让它们能够解决更多现实世界中的问题，比如城市交通网络的最优路线规划、社交网络中的信息传播分析等。在树与图上使用动态规划，就像是在错综复杂的迷宫中，通过标记一个个关键点（状态），找到从起点到终点的最佳路径（最优解）。

树结构上的动态规划

树结构天然具有递归和层次的特性，这使得树的动态规划通常从叶子节点向根节点进行状态转移。我们以 “树的最大路径和” 问题为例来深入理解。

问题描述

给定一棵二叉树，找到从树中某个节点到其他节点的路径中，节点值之和最大的路径。路径可以从任意节点开始，到任意节点结束。

代码示例

#include <iostream>
#include <algorithm>
using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};int maxPathSum(TreeNode* root, int& maxSum) {if (root == nullptr) {return 0;}// 递归计算左子树的最大贡献值int leftMax = max(0, maxPathSum(root->left, maxSum));// 递归计算右子树的最大贡献值int rightMax = max(0, maxPathSum(root->right, maxSum));// 计算经过当前节点的路径和int currentPathSum = root->val + leftMax + rightMax;// 更新全局最大路径和maxSum = max(maxSum, currentPathSum);// 返回当前节点能为父节点提供的最大贡献值return root->val + max(leftMax, rightMax);
}int maxPathSum(TreeNode* root) {int maxSum = INT_MIN;maxPathSum(root, maxSum);return maxSum;
}

代码解释

首先定义了二叉树节点的结构体 TreeNode ，包含节点值 val 以及左右子节点指针 left 和 right 。

maxPathSum(TreeNode* root, int& maxSum) 函数用于递归计算以 root 为根节点的子树的最大路径和。它有两个返回值相关的操作：

函数内部计算当前节点能为父节点提供的最大贡献值。这是通过比较左子树和右子树的最大贡献值（如果为负数则取 0，因为负数不会增加路径和的大小），再加上当前节点的值得到的。比如，leftMax = max(0, maxPathSum(root->left, maxSum)); 就是计算左子树的最大贡献值。

同时，计算经过当前节点的路径和，即当前节点值加上左子树和右子树的最大贡献值，如 int currentPathSum = root->val + leftMax + rightMax; ，并更新全局最大路径和 maxSum 。

外层的 maxPathSum(TreeNode* root) 函数初始化全局最大路径和为最小值 INT_MIN ，然后调用内部递归函数计算并返回最终的最大路径和。

图结构上的动态规划

图的动态规划通常需要处理节点之间复杂的连接关系，常见的有拓扑排序结合动态规划来解决有向无环图的问题，或者使用记忆化搜索处理一般图。我们以 “有向无环图的最长路径” 问题为例。

问题描述

给定一个有向无环图（DAG），图中节点带有权值，找到从某个起点到其他节点的最长路径长度。

代码示例

#include <iostream>
#include <vector>
#include <queue>
using namespace std;// 拓扑排序 + 动态规划求有向无环图的最长路径
int longestPathInDAG(vector<vector<pair<int, int>>>& graph, int start) {int n = graph.size();vector<int> indegree(n, 0);  // 入度数组vector<int> dp(n, 0);  // dp[i]表示从起点到节点i的最长路径长度queue<int> q;// 统计每个节点的入度for (int i = 0; i < n; ++i) {for (auto& edge : graph[i]) {indegree[edge.first]++;}}// 将入度为0的节点入队for (int i = 0; i < n; ++i) {if (indegree[i] == 0) {q.push(i);}}while (!q.empty()) {int node = q.front();q.pop();for (auto& edge : graph[node]) {int nextNode = edge.first;int weight = edge.second;// 更新到下一个节点的最长路径长度dp[nextNode] = max(dp[nextNode], dp[node] + weight);indegree[nextNode]--;if (indegree[nextNode] == 0) {q.push(nextNode);}}}int maxPath = 0;for (int i = 0; i < n; ++i) {maxPath = max(maxPath, dp[i]);}return maxPath;
}

代码解释

首先定义了图的存储结构 vector<vector<pair<int, int>>> ，其中 graph[i] 存储了节点 i 所有的出边，每个 pair 表示目标节点和边的权值。

使用 indegree 数组统计每个节点的入度，dp 数组用于记录从起点到每个节点的最长路径长度。

通过拓扑排序将入度为 0 的节点入队，然后不断从队列中取出节点，更新其邻接节点的最长路径长度（如 dp[nextNode] = max(dp[nextNode], dp[node] + weight); ），并减少邻接节点的入度。当邻接节点入度变为 0 时，将其入队。

最后遍历 dp 数组，找出最长路径长度并返回。

树与图上的动态规划充满了挑战与乐趣，它们在数据结构和算法的世界中扮演着重要角色。通过不断练习和思考，你会发现自己在这片神秘领域中越来越游刃有余。快去探索更多有趣的问题，用动态规划解开它们的奥秘吧！

穿越数据森林与网络迷宫：树与图上动态规划实战指南

在 C 算法的浩瀚宇宙中，树与图就像是神秘的迷宫和茂密的森林，充满了未知与挑战。而动态规划则是我们探索其中的神奇罗盘，帮助我们找到最优路径。今天，就让我们一起深入这片神秘领域，揭开树与图上动态规划的神秘面纱&am…...

编程日记 2025/7/17 11:33:46

Java学习手册：Spring 生态其他组件介绍

一、微服务架构相关组件 Spring Cloud 服务注册与发现 ： Eureka ：由 Netflix 开源，包含 Eureka Server 和 Eureka Client 两部分。Eureka Server 作为服务注册表，接收服务实例的注册请求并管理其信息；Eureka Client 负…...

编程日记 2025/7/17 10:45:31

[android]MT6835 Android 移植brctl指令

说明 android默认brctl不支持showmacs选项，需要移植brctl-utils软件包移除toybox中brctl编译 mssi/external/toybox/Android.bp 将 toybox_symlinks ["[","acpi","base64","basename","blockdev","br…...

编程日记 2025/7/17 11:18:20

initializeViews() 初始化把全部的按钮都弄出来 // 主菜单按钮ImageButton mainButton floatingMenuView.findViewById(R.id.main_button);// 二级菜单按钮subButtons new ImageButton[3];subButtons[0] floatingMenuView.findViewById(R.id.sub_button_1);subButtons[1]…...

编程日记 2025/7/17 10:45:30

HTTP基础介绍+OSI七层参考模型+HTTP协议介绍

图片来源于网络图片来源于网络浏览器 Chrome:谷歌浏览器，推荐 Safari（WebKit）：苹果浏览器，iOS，macOS Firefox：火狐浏览器，开源插件特别多（FireBug） IE:Wi…...

编程日记 2025/7/17 11:11:35

【项目实践】boost 搜索引擎

1. 项目展示 boost搜索引擎具体讲解视频 2. 项目背景对于boost库，官方是没有提供搜索功能的，我们这个项目就是来为它添加一个站内搜索的功能。 3. 项目环境与技术栈 • 项目环境： ubuntu22.04、vscode • 技术栈： C/C、C11、S…...

编程日记 2025/7/17 10:55:12

接口隔离原则（ISP）

非常好，**接口隔离原则（ISP: Interface Segregation Principle）是 SOLID 五大原则中的第四个，它专门解决“一个接口太臃肿”**导致的麻烦。我来从以下几个维度详细拆解： 🧠 什么是接口隔离原则&#xff1…...

编程日记 2025/7/17 10:49:50

Leetcode刷题记录29——矩阵置零

题源：https://leetcode.cn/problems/set-matrix-zeroes/description/?envTypestudy-plan-v2&envIdtop-100-liked 题目描述： 思路一： 💡 解题思路本题中我们采用如下策略： 第一次遍历整个矩阵，记…...

编程日记 2025/7/17 11:13:08

复刻低成本机械臂 SO-ARM100 组装篇（打螺丝喽）

视频讲解： 复刻低成本机械臂 SO-ARM100 组装篇（打螺丝喽） 组装的视频有很多，参考大佬的《手把手复刻HuggingFace开源神作之Follower机械臂组装，资料已整理》_哔哩哔哩_bilibili，跟着视频做，大体…...

编程日记 2025/7/17 11:03:37

[更新完毕]2025东三省B题深圳杯B题数学建模挑战赛数模思路代码文章教学:LED显示屏颜色转换设计与校正

完整内容请看文章最下面的推广群已经更新完整的文章代码基于非线性映射与深度模型的多通道LED显示屏色彩校正摘要本研究聚焦于高动态色彩空间下LED显示屏的色彩映射与逐点校正问题，结合非线性回归理论与深度学习模型，构建了一套涵盖BT.2020映射、RG…...

编程日记 2025/7/17 10:55:12

Easy云盘总结篇-登录注册

**说在前面：该项目是跟着B站一位大佬写的，不分享源码，支持项目付费 ** 获取图形验证码可以看到这里有2两种图形验证码，分为： type0：如上图下面那个，是完成操作后要进行注册的验证码 type1: 如…...

编程日记 2025/7/11 10:18:42

04 基于 STM32 的时钟展示程序

前言我们经常会看到各个场合下面有基于数码管的时钟程序比如在车站, 教室, 办公室等等各个场合都有然后这里就是做一个简单的时钟程序展示程序测试用例每一秒钟更新时间, 然后迭代更新天, 时, 分等等然后主流程基于天, 时分秒渲染数码管 #incl…...

编程日记 2025/7/17 10:51:13

音视频开发技术总结报告

音视频开发技术总结报告一、音视频开发基础 1、音频基础声音原理声波特性：频率、振幅、波长人耳听觉范围：20Hz-20kHz声音三要素：音调、音量、音色数字音频基础采样率：常见44.1kHz、48kHz、96kHz量化位数：8bit、…...

编程日记 2025/7/17 11:02:33

FastAPI系列13：API的安全防护

API的安全防护 1、HTTPS 强制什么是HTTPS强制如何在FastAPI中实现HTTPS强制 2、CORS跨域资源共享什么是CORS在 FastAPI 中开启 CORS 3、SQL注入防护什么是SQL注入如何在FastAPI中实现SQL注入防护 4、CSRF防护什么是CSRF防护如何在FastAPI中实现CSRF防护在 FastAPI系列12&…...

编程日记 2025/7/17 10:51:13

每天一道面试题@第五天

1.包装类型的缓存机制了解么？ 指部分包装类在创建对象时，会将一定范围内的对象缓存起来，当再次使用相同值创建对象时，优先从缓存中获取，而不是重新创建新对象。【提高性能】【节省内存】列举几个常见的包装类缓存机…...

编程日记 2025/7/17 11:08:26

Python硬核革命：从微控制器到FPGA的深度开发指南

1. 重新定义硬件开发：Python的颠覆性突破传统硬件开发长期被C/C++和Verilog/VHDL统治，但Python正通过两条路径改变这一格局： 1.1 微控制器领域的MicroPython革命完整Python 3.4语法支持，运行在资源受限的MCU上（最低要求：64KB ROM，16KB RAM）直接内存访问能力，突破…...

编程日记 2025/7/17 11:19:51

WebRTC 服务器之Janus概述和环境搭建

1 概述 Janus 是由 Meetecho 开发的通用 WebRTC 服务器，它为构建 WebRTC 应用程序提供了一个模块化框架。服务器目标：Janus WebRTC 网关被设计为轻量级、通用的 WebRTC 服务器，除了实现以下方法外，它本身不提供任何功能&#xff1…...

编程日记 2025/6/29 7:27:40

mcp+llm+rag

MCPRAG简介前言一、MCP是什么？二、MCP工作原理（1. MCP Hosts（主机）（2.MCP Clients（客户端）(3. MCP Servers（服务端）(4. Local Data Sources（本地数据源&…...

编程日记 2025/7/9 2:29:24

Seata RM的事务提交与回滚源码解析

文章目录前言一、RM提交事务二、RM回滚事务2.1、undo校验逻辑2.2、执行回滚逻辑总结RM 的事务提交与回滚行为说明（基于 Seata AT 模式）1. 提交阶段（Phase Two Commit）2. 回滚阶段（Phase Two Rollback） 前…...

编程日记 2025/6/29 7:55:25

Ubuntu 24.04 完整Docker安装指南：从零配置到实战命令大全

Ubuntu 24.04 完整Docker安装指南：从零配置到实战命令大全文章目录 Ubuntu 24.04 完整Docker安装指南：从零配置到实战命令大全1. 安装 Docker2. 配置 Docker 镜像加速器2.1 配置 Docker 镜像源2.2 重启 Docker 服务 3. Docker 常用命令3.1 Docker 常用命…...

编程日记 2025/7/5 10:48:56

设计模式简述（十七）备忘录模式

备忘录模式描述组件使用描述备忘录模式用于将对象的状态进行保存为备忘录，以便在需要时可以从备忘录会对象状态；其核心点在于备忘录对象及其管理者是独立于原有对象之外的。常用于需要回退、撤销功能的场景。组件原有对象（包含自身…...

编程日记 2025/6/29 8:14:15

【ICMP协议深度解析】从网络诊断到安全实践

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键报文类型说明协议版本对比二、实战演示环境配置要求核心实验实现实验1：标准ping流程实验2：traceroute路径发现实验3：自定义ICMP…...

编程日记 2025/6/29 7:29:51

《应用开发突围指南：敏捷开发的实战精髓》

如何在应用开发中精准且深入地应用敏捷开发方法呢？让我们一同深入探索。敏捷开发，绝非仅仅是一种开发流程，更是一种蕴含深刻智慧的理念与思维方式。它与传统开发模式有着本质的区别，传统开发模式如同严谨的线性旅程，…...

编程日记 2025/6/29 6:55:14

【Mytais系列】SqlSession

MyBatis 的 SqlSession 是框架的核心接口之一，它是应用程序与 MyBatis 交互的顶层 API，用于执行 SQL 命令、管理事务和访问数据库。以下是关于 SqlSession 的详细说明： 1. 核心功能 (1) 执行 SQL 操作增删改查：通过方法如 sele…...

编程日记 2025/6/29 5:40:33

【掌握 DDL】：SQL 中的数据库与表管理

掌握 DDL：SQL 中的数据库与表管理掌握 DDL：SQL 中的数据库与表管理数据库 DDL创建数据库查看数据库查看所有数据库查看数据库创建语句进入数据库删除数据库备份数据库备份恢复查看数据库连接深入理解数据库创建与删除数据库字符集与校验规则表 DLL创…...

编程日记 2025/6/29 5:19:26

第43周：GAN总结

目录摘要 Abstract 计算机视觉中的分类架构变体损失变体时间序列中的GAN 连续型GAN 离散型GAN 总结摘要本周总结了GAN的变形，主要从图像处理和时间序列生成两部分入手，分别找出了其中比较经典的几种GAN变种模型，简单分析了…...

编程日记 2025/6/29 6:54:31

安卓基础（MediaProjection）

1. Display 类作用：代表显示设备（手机屏幕、外接显示器）常用方法： display.getRotation() // 获取屏幕方向（横屏/竖屏） display.getRefreshRate() // 获取屏幕刷新率（如&…...

编程日记 2025/6/28 20:04:39

Android Compose 物联网（IoT）UI 组件库封装指南

Android Compose 物联网封装组件在物联网(IoT)应用开发中，使用Jetpack Compose可以创建现代化、响应式的用户界面。以下是一些针对物联网场景的Compose封装组件思路和实现方法： 常用物联网组件封装 1. 设备状态指示器 Composable fun DeviceStatusI…...

编程日记 2025/6/29 7:58:58

实用在线工具箱OmniTools

简介 OmniTools 是一个自托管的网络应用，提供多种在线工具，旨在简化日常任务。它包含了一系列独立的、小型但实用的工具，涵盖了文件处理、文本操作、网络请求、系统监控等多个方面。 OmniTools 的设计理念是简单、易用、可定制，方…...

编程日记 2025/6/29 6:34:14

【AI大模型学习路线】第一阶段之大模型开发基础——第三章（大模型实操与API调用）单轮对话与多轮对话调用。

【AI大模型学习路线】第一阶段之大模型开发基础——第三章（大模型实操与API调用）单轮对话与多轮对话调用？ 【AI大模型学习路线】第一阶段之大模型开发基础——第三章（大模型实操与API调用）单轮对话与多轮对话调用&…...

编程日记 2025/6/29 6:37:24

数字化转型进阶：26页华为数字化转型实践分享【附全文阅读】

本文分享了华为数字化转型的实践经验和体会。华为通过数字化变革，致力于在客户服务、供应链、产品管理等方面提高效率，并把数字世界带入每个组织，构建万物互联的智能世界。华为的数字化转型愿景是成为行业标杆，通过推进数字化战略、构建面向业务数字化转型的IT组织阵型、坚…...

编程日记 2025/6/29 5:22:45

Go语言的优势与应用场景 -《Go语言实战指南》

一、 Go语言的五大核心优势 1. 语法简洁，开发高效 Go语言借鉴了C语言的表达方式，但去掉了多余复杂的特性（如继承、多态、异常处理等），语法风格清晰明了，极大地降低了学习成本： • 无需头文件…...

编程日记 2025/6/29 5:25:14

3D人物关系图开发实战：Three.js实现自动旋转可视化图谱（附完整代码）

3D人物关系图开发实战：Three.js实现自动旋转可视化图谱效果核心解析场景初始化自动旋转控制器节点创建（带图片和标签）关系连线动画循环数据格式说明代码效果本文将带您使用Three.js实现一个带自动旋转功能的3D人物关系图谱，核…...

编程日记 2025/6/28 20:04:33

文件操作-

1. 为什么使⽤⽂件？ 如果没有⽂件，我们写的程序的数据是存储在电脑的内存中，如果程序退出，内存回收，数据就丢失了，等再次运⾏程序，是看不到上次程序的数据的，如果要将数据进⾏持久化…...

编程日记 2025/6/29 6:51:44

硬件零基础入门（尚硅谷）

1 一个碳原子有一个自由电子。所以能够导电。金刚石四个都是都弄成共价键了，所以没有自由电子不能自由电子。 2 新的电子进来，因为互斥电荷进行了定向运动，产生了能量。两边电子平衡就停止了。所以电池的负极有电子。电荷就是质子和电…...

编程日记 2025/6/29 6:46:21

【Ai零件】高德开放平台MCP的API-key注册

前言基本操作文档，为n8n等平台，调用高德MCP服务做准备，本文记录其API-Key的生成步骤。操作步骤高德开发平台官网：https://lbs.amap.com/ 完成后，进入控制台界面: 创建新应用进入【应用管理】，点击页…...

编程日记 2025/7/15 21:08:22

安卓基础（startActivityForResult和onActivityResult）

onActivityResult 方法有三个参数： requestCode：启动 Activity 时传入的请求码，用于区分不同的启动请求。resultCode：返回结果的状态码，通常为 RESULT_OK 或 RESULT_CANCELED。data：一个 Intent 对象&…...

编程日记 2025/6/29 5:28:29

安卓基础（悬浮窗）

悬浮窗 import android.app.Service; import android.content.Context; import android.graphics.PixelFormat; import android.os.IBinder; import android.view.Gravity; import android.view.LayoutInflater; import android.view.View; import android.view.WindowManager…...

编程日记 2025/7/15 14:46:44

相关文章：