2022数据结构与算法vol1

2022数据结构与算法vol1

luogu

排序

快速排序

模板题: .

去重复 桶排序

题：

深度优先

八皇后 回溯：

递归 走地图迷宫：

动态规划

求一段最大和

斐波那契

剑指offer 10

题解: .

定长求最大积 |offer14|09-01

剑指offer 14

背包 动态规划

01背包

模板题 P1060：

钱不用花完，求价值最大。

考虑第i种商品，需要在 已经考虑了i-1种、钱一定（从大考虑起）的基础上。 不然的话，从钱小考虑起，后面钱大时，基于的就（有可能）变成i种，钱减一点新加物品（a【j-cost】+value），这就破坏了“考虑第i种”的规则。

一定要装满的01背包

题 P1164：

二维数组，不受上述影响。可以更好得理解状态转移方程。

道理是一样的，关于装满，改变 状态转移方程 的思路即可。

线性动态规划

最长单调序列

P1020:

升序再降序

P1091:

分治

快速幂 模板题

P1226:

贪心

合并最小 + 题解 扩展（小根堆/优先队列；桶排序）

P1090： sort，数组里swap

贪心ex

平均等待时间最小

p1223:

均分纸牌 相邻移动

p1031:

递推与递归二分

本质上类似走迷宫的树 略微剪枝

p1025

台阶的走法，dfs会爆掉，用递推公式 & 推荐用dp & 另有快速幂

p1192

广度优先，用多个一维数组实现队列 + 题解可以学stl & 泪目 近期第一个自己写的

p1135