带有标签的文章：

#动态规划

10篇文章

子图最短路

给定带权无向图，对每个点编号区间\([\ell,r]\)，取仅包含区间内点的导出子图；子图中点对不连通距离视为 0，求所有区间内全部\(u\le v\)点对的子图最短路总和，对\(10^9\)取模，\(n\le100\)。

将 n 名同学划分为若干个学习小组，每个小组的综合积极度由基础积极度 a_k 加上组内发言积极度最大值与最小值之差组成，要求求出所有划分方案中各小组综合积极度之和的最大值。

将 n 名同学划分为若干个学习小组，若小组人数为 k 则产生 a_k 的积极度，要求求出所有划分方案中各小组积极度之和的最大值（本质为完全背包问题或线性动态规划问题）。

本题要求在一张无向加权图中寻找所有重要城市：若摧毁某节点会导致至少一对其他节点之间的最短路径变长或不可达，则称该节点为重要城市。

在不超过背包容量 W 的前提下，从 n 种可无限次重复选择的物品中挑选物品（每种物品重量为 w_i，价值为 v_i），求能装入背包的物品总价值最大值。

给定 n 种数量有限（第 i 种最多取 c_i 个）的物品装入容量为 W 的背包中，要求在总重量不超过背包容量的前提下，使得装入物品的总价值最大。

将 n 种各只有一件的物品装入容量为 W 的背包中，每种物品只能选择装或不装，要求在总重量不超过背包容量的前提下，使得装入物品的总价值最大。

Floyd‑Warshall 算法是基于动态规划的全源最短路径算法，可求解图中任意两点最短距离，支持负权边，适合小规模稠密图，也能够检测图中的负权环。

增量式 Floyd 在标准 Floyd 基础上，按顺序逐步加入中间节点 k，动态更新任意两点间最短路径，支持节点逐个新增的场景；它复用之前已算好的路径结果，不必每次从头完整重跑，适合图中节点不断增加的问题，时间复杂度仍为\(O(n^3)\)。

斐波那契数列指从 0、1 开始，后续每一项都等于前两项之和的数列，即 0，1，1，2，3，5，8……，它频繁出现在植物生长、自然形态中，同时在算法、递归、黄金比例相关问题里有着广泛应用。