【十八】动态规划之——最长上升子序列模型


2、最长上升子序列模型(LIS: Longest Increasing Subsequence)895. 最长上升子序列题目链接题目给的数据范围是1000,所以我们可以用 dp 来做,通过闫氏dp分析法 从集合角度分析,如下根据上面dp分析,实现代码如下#include <iostream&g

【十七】动态规划之——数字三角形模型


动态规划闫氏DP思考法:从集合角度来考虑DP 问题。状态计算重要的划分依据:依据最后一步来划分集合集合划分原则:不重复、不遗漏在求Min/Max, 可以忽略到 不重复这个原则,因为重复对Min和Max的结果不会照成影响计算顺序:计算时我们必须要保证当前状态需要用到的状态,必须已经被提前计算了。1、数

【十六】乘法逆元


定义证明通过费马定理证明

【十五】欧拉函数与欧拉定理


欧拉函数定义证明应用题目:欧拉函数 #include <iostream> #include <algorithm> using namespace std; using LL = long long; int main() { int t; c

【十四】约数


能整数该数的数就是约数试除法求约数vector<int> get_divisors(int x){ vector<int> res; for (int i = 1; i <= x / i; i ++ ) if (x % i == 0)

【十三】质数


质数大于1的自然数,只能被1和它本身整除的数就是质数。任何一个合数都能表现成多个质数的乘积。判断质数很明显判断一个数是不是质数,我们只需要判断它只有1和它本身这两约数。试除法朴素做法判断一个数x是否是质数,就枚举小于x的数去试除法。for (int i = 2; i < x; ++ i) {

【十二】二分图


二分图指的是,把图中所有的点划分成两个集合。集合内部不存在边,边只存在两个集合之间。这个有点像鞋带的就是二分图。二分图的一个性质:一个图是二分图,当且仅当图中不包含奇数环(指环中的边的数量是奇数)。因为,我们很可以推测出当存在一个奇数环,我们不可能把一个点划分到两个集合中。图下就矛盾了。该点不能同时

【十一】最小生成树


最小生成树,指的属于该生成树的任意一个点,到生成树其他任意的点距离最短或权重最小或代价最小。普利姆算法(Prim)算法思想用dist维护距离最小生成树集合的最短距离,每次选择dist中,未在集合中且距离集合最短的点。然后,把这个点加入集合,用这个点更新其他点到集合的距离。整理的思想根dijkstra

【十】最短路


最短路算法分类单源最短路单源最短路,就是只有一个固定的起点。无负权边所有边中不存在负权边朴素Dijkstradijkstra 是基于 贪心算法的,当存在负权边的时候,局部最优不能代表全局最优解算法思想维护一个最短路集合st,每次选择未进入最短路集合中距离x点最短距离的点。把这个点加入最短路集合st中