/tag/graph-theory
graph-theory
2 篇文章带着 graph-theory 这个标签。
2 articles
[CSP-S 2019 T2] 括号树
[[CSP-S 2019 T2] 括号树](https://www.luogu.com.cn/problem/P5658) 题意 给定一颗 n 个节点的树，每个节点有一个括号 ( 或者 )，现在询问 i 节点到根节点这一条链上所有括号组成的括号序列有几个子括号序列合法 对题目进行分析 观察 1 定义 f(x) 为以 x 节点结尾的合法括号序列数，很容易想到 $[1,i]$…
Dynamic Programming on Graphs
A篇：图论DP思维框架与状态设计 A1 图论DP核心方法论 A1.1 状态图视角 — 用有向无环状态图理解最优子结构与重复子问题 动态规划经常被描述为“记忆化搜索”或“递推填表”，但这些说法容易让人忽略一个更本质的图景：每一个动态规划问题都天然对应一张有向无环图，这张图将问题拆解为节点，将依赖关系刻画为边。当我们把动态规划看作在这张状态图上寻找最优路径的过程，最优子结构与重...