线性dp dp就是填表格,先通过初始化一些已知的值,然后通过状态转移方程来转移到下一个位置 数字金字塔 这题要求我们从数字金字塔中找到一条路径由最高点走到最低点,使经过的数字的数字数值最大. 做法之一就是dfs,但是时间复杂度O(2^n). 使用dp,时间复杂度为O(n^2). 首先初始化一个矩阵,用来存储金字塔,接着初始化一个dp[i][j]数组…

双向搜索 同时从起点和终点启动搜索,碰头就停止,并通过一定公式合并两端的数据. 优化搜索深度,从而优化时间复杂度. 双向dfs 异或路径 启动前半部分搜索. 启动后半部分搜索. 合并答案. #pragma GCC optimize(2) #pragma GCC optimize("avx") #pragma GCC optimi…

深度优先搜索 顾名思义 优先往深处走的搜索就是深度优先搜索 主要用栈实现 例如这张图 我们依次走过每个点 深度优先搜索就是 1 2 5 9 此时已经到达最深处了,无路可走了,就要往回探索,称之为回溯. 回溯到5 发现10还没走过,再接着探索10. 依次类推 回溯到2时 探索 6. 迷宫 该问题要求我们求出一个迷宫是否有解,使用深度优先搜索解决,每次…

选择排序 时间复杂度O(n^2) 空间复杂度O(n) 不稳定排序 具体原理: 每次选择一个最小或最大的数放进排序后的数组中 void sectionSort(int n, int a[], bool flag) //选择排序 { int* b = new int[n + 50]; memset(b, 0, (n + 50) * sizeof(int…

前缀和 前缀和通过一个数组记录到当前位置所有的和,以此来快速计算出该数组中一段区间的和 计算方法如下: sum[i] = a[0] + a[1] + ... + a[i] sum[i] = sum[i - 1] + a[i] - 通过构建完前缀和数组,我们就可以在O(1)的时间复杂度中查询a[l,r]的和: - sum[r] - sum[l-1] …

二分 若有一串有序数列,想要查询其中一个数的位置,最快的方法显然就是折半查找,若当前数大了,就往小的找,若当前数小了,就往大的找,这就是二分查找. 如果有一种材料,想要找到他最大的承受能力,此时该材料可承受的力可以为1 2 3 4.... 是一串有序的数列,我们只需要指定一个最大值和最小值,在该范围内进行二分,如果还能承受就多加一些,如果不能承受就…

贪心 只考虑当前的最优情况,而不考虑未来. 排队接水 每次都找接水时间最短的一人来接水就可以解决问题. #include <bits/stdc++.h> using namespace std; struct w { int id; int time; }water[1005]; bool cmp(const struct w &…

模拟 模拟是指让程序完整的按照题目叙述的方式执行运行得到最终答案 校门外的树 #include <bits/stdc++.h> using namespace std; int trees[10086]; int main() { int m,n; cin >> m >> n; for (int i = 1 ; …

二叉搜索树(Binary Search Tree) 二叉搜索树(BST)是一种二叉树的树形数据结构。 定义如下： 空树是二叉搜索树 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值 二叉搜索树的左右子树均为二叉搜索树 二叉搜索树上的基本操作所花费的…

1.倍增 #include <iostream> const int N = 100000 + 5000; const int M = 21; int a[N]; int t[N]; int n; int f[N][M];//从第i站转车2的j次方到的站 int g[N][M];//从第i站专车2的j次方到的站用的时间 void ini…