题型与解法

今天药忘吃喽~ 2022-07-11 14:30 260阅读 0赞

我对本文的定位是题型. 高手请忽略.

本文会随时进行必要的更新, 如果你有一些经典题目和一些经典题型, 请您一定告诉我哟~

部分摘自黑书.

动态规划

动态规划的两种动机:

1. 利用递归的重叠子问题,进行记忆化求解,即先用递归法解决问题,再利用重叠子问题转化为动态规划.

例,

1)括号序列

2)棋盘分割

3)决斗

2. 把问题看成多阶段决策过程.

例,

1)舞蹈家怀特先生

2)积木游戏

可以通过增加维数的方法来消除后效应, 也可以在保持无后效应性的前提下改变状态定义,以得到更多的重叠子问题.

当问题不具备最有子结构时,通常通过增加维数的办法来解决.

常见模型:

1. 线性模型

例,

1)方块消除

2)公路巡逻\*

3)并行期望值\*

4)高性能计算\*

2. 串模型

1)模板匹配(常为s\[i\]\[j\] 和 s\[i\]\[j-1\] s\[i-1\]\[j\]的关系)

2)不可分解的编码\*

3. 区间模型

1)青蛙的烦恼(常为d\[s\]\[L\]\[x\]从s起长度为L的一个区间, 对于某些特定问题,x可以用来选择区间的起点)

2)排列问题

3)最优排序二叉树\*

4.状态压缩模型

1)Bugs公司\*

2)迷宫统计\*

3)贪吃的九头蛇\*

我的分类:

一. 递归向下分解成更小的问题, 转化为动态规划向上

1. 分苹果问题(pku 1664)

2. 整数分割问题(王晓东<<算法分析与设计>>)

3. 买书问题(编程之美1.4可以看到这道题)

二. 背包问题

贴一份源代码:

\#include <iostream> \#include <algorithm> using namespace std; \#define N 4 \#define W 6 int opt\[N+1\]\[W+1\]; //i:0~N-1, j:0~V int w\[N+1\] = \{1,2,3,4\}; int v\[N+1\] = \{0,2,4,5\}; //用后i-N+1个物品(i,i+1,...N-1), 包的容量为j时的最大价值. //写法一, 较麻烦 int knapsack() \{ int tmp = min(w\[N-1\], W); for(int i = 0; i < tmp; ++i) opt\[N-1\]\[i\] = 0; for(int i = w\[N-1\]; i <= W; ++i) opt\[N-1\]\[i\] = v\[N-1\]; for(int i = N-2; i >= 0; --i) for(int j = 0; j <= W; ++j) \{ opt\[i\]\[j\] = opt\[i+1\]\[j\]; if(j >= w\[i\]) \{ int value = opt\[i+1\]\[j-w\[i\]\] + v\[i\]; if(value > opt\[i\]\[j\]) opt\[i\]\[j\] = value; \} \} return opt\[0\]\[W\]; \} //写法二, 稍微简略 int knapsack2() \{ for(int i = 0; i <= W; ++i) opt\[N\]\[i\] = 0; for(int i = N-1; i >= 0; --i) for(int j = 0; j <= W; ++j) \{ opt\[i\]\[j\] = opt\[i+1\]\[j\]; if(j >= w\[i\]) \{ int value = opt\[i+1\]\[j-w\[i\]\] + v\[i\]; if(value > opt\[i\]\[j\]) opt\[i\]\[j\] = value; \} \} return opt\[0\]\[W\]; \} //节省空间 int space\_opt\[2\]\[W+1\]; int space\_opt\_knapsack() \{ int tmp = min(w\[N-1\], W); for(int i = 0; i < tmp; ++i) opt\[0\]\[i\] = 0; for(int i = w\[N-1\]; i <= W; ++i) opt\[0\]\[i\] = v\[N-1\]; int cc = 1; for(int i = N-2; i >= 0; --i) \{ cc = 0?1:0; for(int j = 0; j <= W; ++j) \{ opt\[(cc+1)%2\]\[j\] = opt\[cc%2\]\[j\]; if(j >= w\[i\]) \{ int value = opt\[cc%2\]\[j-w\[i\]\] + v\[i\]; if(value > opt\[(cc+1)%2\]\[j\]) opt\[(cc+1)%2\]\[j\] = value; \} \} \} return opt\[cc\]\[W\]; \} //备忘录法(又称记忆化搜索), 不需要计算的不做计算 int f(int i, int j) \{ if(i == N) return 0; if(opt\[i\]\[j\] != -1) return opt\[i\]\[j\]; if(j >= w\[i\]) return max(f(i+1, j-w\[i\])+v\[i\], f(i+1, j)); else return f(i+1, j); \} void knapsack\_recursion\_test() \{ memset(opt, -1, sizeof(opt)); cout << f(0, W) << endl; \} int main() \{ knapsack\_recursion\_test(); return 0; \}

哈希法

一. 直接哈希, 相当于打表, 不再多言

二. 直接哈希的空间优化

当某些元素已经不必要时, 我们将其删除, 以减小空间的消耗

比如, 在几G空间中, 只有一个数出现了一次, 其他都出现了两次, 对其进行hash, 每当一个ID出现两次后, 可以将其空间释放.

异或运算的运用

一. 利用异或寻找数列中出现奇数次的数

问题: 在几G空间中, 只有一个数出现了一次, 其他都出现了两次, 找出这个数?

因为有A^A=0 A^0 = A, 我们可以把所有数做异或运算, 所以我们可以找出这个数.

问题: 在几G空间中, 所有数都出现了两次, 结果丢失了两个数, 如何找出这两个数A, B?

我们可以把所有数做异或运算, 如果结果为0, 那么说明丢失的是两个相等的数(A=B);

否则, 丢失的是不同的两个数, 所有数的异或不为0, 其结果必有一位为1, 那么A,B有且就有一个的这一位也为1.