简介 数字三角形类问题的特点是当前状态可以由上一行计算出的状态得出，在之前写的一篇文章中记录过，本文记录两道基于数字三角形模型的实际问题。 方格取数 设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。 某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。 在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。 此人 ...

分割棋盘 求把 N x M 的棋盘分成若干个 1 x 2 的长方形有几种方案。 题目链接：AcWing 291。 把某种状态以一个二进制数表示出来就是状态压缩，这里用一个二进制数储存在 n 行中有哪些长方形伸了出来，这里设 n 行 m 列，分析如下： 状态表示 f[i, j]： 含义：第 i 列中从 i-1 列中伸出来了状态为 j 的横着放的长方形的方案。由于剩下的位置只有竖着放长方形这一 ...

简介 本文包含数字三角形问题、最长上升子序列问题的几道基础例题，更多内容参考本站其它相关文章。 然后把一些不好分类的题也写在这里了。 数字三角形 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 12345 7 3 8 8 1 0 2 ...

01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。 原题：AcWing 2。 动态规划最入门的问题，我们开辟一个二维数组 f[i][j]，它的含义是在前 i 个物品中在体积最大为 j 的基础上的最优解。 可以得到状态转移方程：f[i][ ...

简介 二分图指的是可以把点放到两个集合中，并且集合中不存在边。染色法可以判断一个图是否为二分图，匈牙利算法可以求出二分图最大匹配。匹配指的是二分图中任意两条边都不依赖于同一个顶点的一个子图，简而言之就是在这两边连线不能重复连同一个点，求这些连线的个数。 染色法判定二分图 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。 请你判断这个图是否是二分图。 用 DFS 染色，每个节点和它 ...

简介 最小生成树问题是指用图中所有节点构造一个边权重之和最小的树，可以用 Prim 算法和 Kruskal 算法解决稠密图和稀疏图的最小生成树问题。 Prim 给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。 求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。 Prim 算法适用于稠密图，与 Dijkstra 算法思想一致，基本思路如下 ...

简介 对于最短距离问题，一共有如下几种算法： Dijkstra 算法是用来计算单源正权最短路算法，它的朴素版适用于稠密图，复杂度 O(n2)O(n^2)O(n2)；堆优化版适合稀疏图，复杂度 O((n+m)log⁡n)O((n+m)\log n)O((n+m)logn)。 Bellman-ford 算法用来解决**（有边数限制）的含负权最短路问题**，如果有边数限制一般就只能用此算法求解，复杂度 ...

简介 该数据结构的作用有如下两点： 合并两个集合。 查询两个元素是否在同一个集合中。 基本实现原理是把每个集合用一颗树表示，树根的编号是这个集合的编号，每个节点都存储它的父节点，p[x] 表示 x 的父节点，对于根节点，p[x] = x。 对于优化，可以在查找树根时将路径上的每一个节点的父节点都指向树根。 例题 一共有 nnn 个数，编号是 111 ~ nnn，最开始每个数各自在一个集合中。 ...

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀。

在 C++ 中用数组来模拟单双链表，这样的方式也被称为静态链表，下面以两例题记录 C++ 中的链表应该如何定义和使用。