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

区间选点 给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。位于区间端点上的点也算作区间内。 题目链接：AcWing 905。 先把区间按照右端点排序，然后每个区间尽量选择右端点，如果选过的点包含了当前区间则跳过，因为这样选择之后一定会选中 M 个不相互重叠的区间，想覆盖这些区间的最小点数一定是 M： 12345678 ...

分割棋盘 求把 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][ ...

快速幂 快速幂是在 O(log⁡k)O(\log k)O(logk) 的复杂度下计算 ak mod pa^k\bmod pakmodp 的结果。 可以用二进制的方式理解，令 k=∑bi2ik=\sum b_i2^ik=∑bi​2i，那么 ak=a∑bi2i=∏(a2i)bia^k=a^{\sum b_i2^i}=\prod (a^{2^i})^{b_i}ak=a∑bi​2i=∏(a2i)bi​，所 ...

简介 二分图指的是可以把点放到两个集合中，并且集合中不存在边。染色法可以判断一个图是否为二分图，匈牙利算法可以求出二分图最大匹配。匹配指的是二分图中任意两条边都不依赖于同一个顶点的一个子图，简而言之就是在这两边连线不能重复连同一个点，求这些连线的个数。 染色法判定二分图 给定一个 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 算法用来解决**（有边数限制）的含负权最短路问题**，如果有边数限制一般就只能用此算法求解，复杂度 ...

简介 Hash 的思想就是设计函数 f(A)f(A)f(A) 将某个数据类型映射为整数，由于相同的元素映射后得到的值仍然相同，所以当 f(x)=f(y)f(x)=f(y)f(x)=f(y) 时认为 x=yx=yx=y 即 Hash 的思想。 为了防止哈希碰撞即 f(x)=f(y)f(x)=f(y)f(x)=f(y) 时 x≠yx\ne yx=y，可以多设计几个函数 f1,f2,…f_1,f_2, ...