猛兽总是独行，牛羊才成群结队 (真的是鲁迅说的)
核心思想
递推
感觉难就难在递推式不好找，或者是代码不好设计，没办法多做多练吧~
入门：最简单的递推：斐波那契数列
F[n]=F[n-1]+F[n-2]
每一步都由其他步推出，这就是递推
进阶：爬楼梯与错排公式
给出一段楼梯，每次可以爬两阶或者一阶，问共用多少种不同不同的爬楼方法
爬楼梯分析
对于每一层的楼梯 我们这样来分析：
- 爬到终点阶数的方法总数 = 少两阶的方法总数（一次爬两阶到达终点） + 少一阶的方法总数（一次爬一阶到达终点）
这就有点递归的意思了，但实际上可以不用递归
因为阶数多了以后数会非常大，所以这种题一般求得都是取模后的结果
道理是一样的，只需要知道：
- a % c + b % c = (a + b) % c;
所以直接每步都直接模就行~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#include <cstdio>
using namespace std;
const int mod = 100007;
int dp[1010];
int (){
int n;
cin >> n;
dp[1] = dp[0] = 1;
for(int i = 2; i <= n; i++){
dp[i] = (dp[i - 1] + dp[i - 2]) % mod;
}
cout << dp[n] << endl;
return 0;
}
|
说到递推不得不提著名的错排公式了：
十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用D(n)表示，那么D(n-1)就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
- 第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
- 第二步，放编号为k的元素，这时有两种情况：⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有D(n-2)种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有D(n-1)种方法；
综上得到
D(n) = (n-1) [D(n-2) + D(n-1)]
特殊地，D(1) = 0, D(2) = 1.
以上，这也是一种递推
递推与动态规划
动态规划的属性
- 阶段：把求解的问题分为若干个阶段
- 状态：每个阶段面临的各种客观条件（个人人为状态在寻找递推公式中最为重要）
- 决策 在每个阶段做出的不同操作
- 状态转移方程 由i阶段的状态和决策决定i + 1阶段的状态
- 策略 各个阶段决策的序列
回家的最短路径问题
只看递推着实是简单了点，下面难度提升啦
A菌要回家，他家在一个n * n地图的左下角，家在右上角，没走上一个格子会花费一定的体力，每一步都只能走到上面说左面的相邻格子上，耗费的体力值标注在了地图上：
第一行是地图大小n 接下来n行是地图的描述
对于此题，一样是递推，考虑：
走到每个格子上一共需要耗费的体力，要么是从这个格子的左面走过来，要么是从这个格子的下面走过来
所以我们只需要分别知道当走到 ”每个格子的左面和下面的格子所需要消耗的体力即可”
这里的每个格子的下面和左面，体现了递推的过程。
在代码中我定义了动态规划数组dp用来记录走到每个格子最少所需花费体力，具体计算方法是在循环中递推出每个格子的左，下格的最少体力并进行决策
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <algorithm>
using namespace std;
int a[110][110];
int dp[110][110];
int () {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
dp[1][1] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == 1 && j == 1){
continue;
}
else if(i == 1){
dp[i][j] = dp[i][j - 1] + a[i][j];
}
else if(j == 1){
dp[i][j] = dp[i - 1][j] + a[i][j];
}
else{
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
}
cout << dp[n][n] << endl;
return 0;
}
|
难度提升：爬楼梯增强版及其他
爬楼梯增强版
难就难在递推公式不好想，其实仔细想想，递推公式和普通爬楼梯是一样的，都是：
dp[i] = dp[i - 2] + dp[i - 1];
只不过这个题要提前规定好dp[1] - dp[3]的值
1
2
3
|
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
|
或者先写出前几阶的结果，然后照着规律蒙一下。
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
using namespace std;
int dp[10005];
int n;
int (){
cin >> n;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
for(int i = 4; i <= n; i++){
dp[i] = dp[i - 2] + dp[i - 1];
dp[i] = dp[i] % 100007;
}
cout << dp[n] << endl;
}
|
弹簧板
这是比较友好的一道题了：
分析：
递推公式很好找，只不过是从后往前推，当小球从最后一块板子开始，那么很显然只能跳一次
对于其他前面的板子，只要后面跳到了最后一块板子上，都可以直接加上最后一块板子已经计算出来的数值1（这里是递推的过程）
再比如，此时已知从中间的某一块弹簧板开始跳出的步数，那么这块弹簧板之前的所有板子在跳到这块已知的弹簧板上时都只需将步数加上即可
得出递推公式：
1
|
dp[i] = dp[i + a[i]] + 1;
|
因此从后面的板子一步一步往前推，最后把从每块板子上开始的值计算出来输出最大即可
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
#include <cstring>
using namespace std;
int n;
int dp[100035];
int a[100035];
int (){
cin >> n;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int ans = 0;
for(int i = n; i >= 1; i--){
dp[i] = dp[i + a[i]] + 1;
ans = max(ans, dp[i]);
}
cout << ans << endl;
}
|
传娃娃游戏：
笨办法，队列暴力求解
难度稍微上升了一点点，刚刚拿到题目一看就想着暴力求解，直接一个队列下去，把每个同事A所能传到的同事全部入队，再把A出队，最后看一下队列里剩下的人有多少个是开始的那个人
时间复杂度不算高，数据量只有30可以承受，但是内存受不了了，每个同事能传给两个同事，2的30次方是个多么大的数简直不敢想，数据量上去了耗时也就上去了，理所当然过不了
以下是纯用队列的做法，小孩子不要轻易模仿噢😯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include <queue>
using namespace std;
struct node {
int n;
int step;
node(int _n ,int _step){
n = _n;
step = _step;
}
};
int n, m;
int (){
cin >> n >> m;
queue<node> q;
int now = 1;
q.push(node(1, m + 1));
for(int i = m; i >= 1; i--){
while(q.front().step == i + 1){
now = q.front().n;
q.pop();
if(now - 1 == 0){
q.push(node(n, i));
}
else{
q.push(node(now - 1, i));
}
if(now == n){
q.push(node(1, i));
}
else{
q.push(node(now + 1, i));
}
}
}
int ans = 0;
while(!q.empty()){
if(q.front().n == 1){
ans++;
}
q.pop();
}
cout << ans << endl;
}
|
递推
还是倒着推：假设最后和开始拿到娃娃的都是1号同事，那么他上一步给他娃娃的一定就是 n 号同事或者 2 号同事，在上一步呢？
一步一步推回去
前面提到了动态规划的五条属性，这里的状态分别为;
- 这一阶段是传递过程中的第几次
- 这一阶段传递到某一同事的总路线有几条
用两个状态定义数组f[]
除此之外，递推公式也要分为三种情况，此阶段拿娃娃的同事如果是1号或者是n号的情况，也需要单独考虑。
根据以上分析，就不难写出递推式了，下面给出源码：
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>
using namespace std;
int f[35][35];
int main(){
int n, m;
cin >> n >> m;
f[0][1] = 1;
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(j == 1){
f[i][j] = f[i - 1][2] + f[i - 1][n];
}
else if(j == n){
f[i][j] = f[i - 1][1] + f[i - 1][n - 1];
}
else{
f[i][j] = f[i - 1][j - 1] + f[i - 1][j + 1];
}
}
}
cout << f[m][1] << endl;
}
|
墙壁涂色
这题看起来和传娃娃有一点点像，但我用了完全不同的分析思路，其实也是有难度的。
分析：
一开始可能只是想纯用数学的排列组合的方式得出求解公式，但是我自己也忘得差不多了不会算
此题的整个涂色方法类似一个二叉树，只不过最后需要删掉几个和根节点值一样的叶子
所以两个状态：
- 涂色涂到了第几阶段
- 此阶段与起始（根节点）值相同的路线有几条
不难发现，每个阶段与根节点值相同的叶子的数量等于上个阶段与根节点值不同的叶子数
所以在上面已分析出的状态上我们还要细分出每个阶段两种叶子的数量这一状态
下面看源码
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include <iostream>
using namespace std;
int main(){
int n;
long long room[55][2];
cin >> n;
room[n][0] = 1;
room[n][1] = 0;
room[n][3] = 1;
for(int i = n - 1; i >= 1; i--){
room[i][0] = room[i + 1][1];
room[i][2] = (room[i + 1][0] + room[i + 1][1]) * 2;
room[i][1] = room[i][2] - room[i][0];
}
cout << room[1][1] * 3 << endl;
}
|
逃生
此题可以看做是最简单的回家最短路径递推的复杂版，分四个路线分别递推出去，注意审题，有很多限制条件，简单，非常简单(不配做30分的题)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include <iostream>
using namespace std;
int n, m, x, y, v, c;
int map[1010][1010];
int dp[1010][1010];
int main(){
cin >> n >> m >> x >> y >> v >> c;
for(int i= 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> map[i][j];
}
}
dp[x][y] = v;
for(int i = x; i >= 1; i--){
for(int j = y; j >= 1; j--){
if(i == x && j == y){
continue;
}
if(i == x){
dp[i][j] = dp[i][j + 1];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
if(j == y){
dp[i][j] = dp[i + 1][j];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = min(dp[i][j] + map[i][j], c);
if(dp[i][j] <= 0){
dp[i][j] = -1000000;
}
}
}
for(int i = x; i >= 1; i--){
for(int j = y; j <= m; j++){
if(i == x && j == y){
continue;
}
if(i == x){
dp[i][j] = dp[i][j - 1];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
if(j == y){
dp[i][j] = dp[i + 1][j];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
dp[i][j] = min(dp[i][j] + map[i][j], c);
if(dp[i][j] <= 0){
dp[i][j] = -1000000;
}
}
}
for(int i = x; i <= n; i++){
for(int j = y; j >= 1; j--){
if(i == x && j == y){
continue;
}
if(i == x){
dp[i][j] = dp[i][j + 1];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
if(j == y){
dp[i][j] = dp[i - 1][j];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]);
dp[i][j] = min(dp[i][j] + map[i][j], c);
if(dp[i][j] <= 0){
dp[i][j] = -1000000;
}
}
}
for(int i = x; i <= n; i++){
for(int j = y; j <= m; j++){
if(i == x && j == y){
continue;
}
if(i == x){
dp[i][j] = dp[i][j - 1];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
if(j == y){
dp[i][j] = dp[i - 1][j];
dp[i][j] = min(dp[i][j] + map[i][j], c);
continue;
}
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
dp[i][j] = min(dp[i][j] + map[i][j], c);
if(dp[i][j] <= 0){
dp[i][j] = -1000000;
}
}
}
int temp1 = max(dp[1][1], dp[1][m]);
int temp2 = max(dp[n][1], dp[n][m]);
int ans = max(temp1, temp2);
if(temp1 < 0 && temp2 < 0){
cout << -1 << endl;
return 0;
}
cout << ans << endl;
return 0;
}
|
一维消消乐
两个状态：
其他分析写在注释里，看源码：
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>
using namespace std;
int main(){
int f[10005];
int dp[10005][2];
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> f[i];
}
dp[1][0] = 0;
for(int i = 2; i <= n; i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + f[i - 1] * f[i];
}
cout << max(dp[n][0], dp[n][1]) << endl;
return 0;
}
|
小朋友过河问题
分析
一看这道题样例怎么想也觉得应该是19而不是17
我考虑的是每次都是最小的带着当前最大的过去然后最小的回来（但是这样实在太简单了不可能）
其实还有一种比较快的方法：先让最小的带着第二小的过河，然后每次过河两个最大的，第二小的再回来 ，这样有可能会比每次都由用时最小的人带最大的过去快。这就需要决策了
所以先排一个序，每次要么是第一种过河方法
1
2
|
dp[i - 1] + a[0] + a[i] ;
|
要么是第二种过河方法：
1
2
|
dp[i - 2] + a[i] + a[1] + a[1] + a[0];
|
以上就是状态转移方程
下面给出源码：
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int x, int y){
return x < y;
}
int main(){
int n;
cin >> n;
int a[1005];
int dp[1005];
for(int i = 0; i < n; i++){
cin >> a[i];
}
sort(a, a + n, cmp);
dp[0] = a[0];
dp[1] = a[1];
for(int i = 2; i <= n; i++){
dp[i] = min(dp[i - 1] + a[0] + a[i], dp[i - 2] + a[1] + a[1] + a[i] + a[0]);
}
cout << dp[n - 1] << endl;
return 0;
}
|
毕业题（个人觉得会做这道题入门的动态规划学习算是毕业了）数组分组
分析：
还是先看状态
- 递推到了第几个数（阶段）
- 在当前阶段下决策出的最大权值和
对于每个阶段，由于我们已经知道了前面所有阶段的最大权值和：
所以只需要在当前阶段中组合最后一组，与前面已经算好的对应的各阶段权值和相加，决策出最后一组数字组合与其对应的前面其他组的全职和即可
另外，关于最后一组数字和的遍历不应每次单独计算，太浪费时间，直接在开始动态规划之前初始化出来（代码中用pre数组存储）
分析可能读起来会很难懂，请结合代码：
源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
using namespace std;
int a[1005];
int dp[1005];
int pre[1005][1005];
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
pre[i][i] = a[i];
}
for(int i = 1; i <= n; i++){
for(int j = i + 1; j <= n; j++){
pre[i][j] = pre[i][j - 1] * a[j] % 1000;
}
}
dp[1] = pre[1][1];
for(int i = 2; i <= n; i++){
dp[i] = pre[i][i];
for(int j = i - 1; j >= 0; j--){
dp[i] = max(dp[j] + pre[j + 1][i], dp[i]);
}
}
cout << dp[n] << endl;
}
|
3月23日更新：今天重做了这道题，把以前没个状态下的判断最大值改成状态转移方程dp[i] = max(dp[j] + pre[j + 1][i], dp[i]);
更容易理解！
至此，入门动态规划练习结束٩( ๑╹ ꇴ╹)۶
近期评论