DP入门

发表于 | 更新于: | 次
字数统计: 692 字 | 阅读时长 ≈ 2 分钟

耗费了两晚上的时间( 还有紫书的帮助 )，终于理解了动态规划的实现，或者说详细步骤？大概吧，这对于理解力强的大佬来说没什么难度

动态规划的核心很多文章都有讲到，就是一个状态转移方程，这方面我也不多说了，可以自行百度

这个状态转移方程对于初学者来说或许不难，但是会很难理解详细的实现步骤，下面上一个模板题，简单讲一下遍历过程

[IOI1994][USACO1.5]数字三角形 Number Triangles

这个题在当年据说难倒了国家队队员，现在已经是萌新入门拿来练手的题了

核心方程

详细的题目我不在这里赘述，下面贴代码(这只是其中一种做法，递推实现)，我用的是二维数组，方便理解，可以优化成一维

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
#include<bits/stdc++.h>
#define FOR(x,k,z) for(register int x = k; x <= z; x++)
typedef long long int64;

using namespace std;

int r;//三角形的高
int tree[1005][1005];//用来存入三角形，同时用于存放从[y][x]点出发能得到的最大值

int main()
{
	cin >> r;//输入三角形高度
	FOR(i, 1, r)//读入三角形，可以用快读，但是这题不用，cin的速度完全够用
	{
		FOR(j, 1, i)
		{
			cin >> tree[i][j];
		}
	}
	for(register int i = r - 1; i >= 1; i--)//这里是逆序循环，也就是说从底层往上走，如果看不懂可以看我下面的手动模拟
	{
		FOR(j, 1, i)
		{
			tree[i][j] += max(tree[i + 1][j], tree[i + 1][j + 1]);//核心代码
		}
	}
	cout << tree[1][1];//递推到最顶端的一个一定是正解，因为要从顶端往下走，顶端又只有一个数
	return 0;
}

为什么要从倒数第二层开始推呢？

因为倒是第二层再往下就是最后一层了啊(雾

举个例子

​ 7
​ 3 8
​ 8 1 0
2 7 4 4
4 5 2 6 5

我们从倒数第二层开始找，2可以和4或5相加，很明显，5是最优解，于是我们在tree(4)(1)存入2 + 5 = 7

倒数第二层还没找完，我们继续从7开始找，7可以和5或2相加，5是最优解，于是在tree(4)(2)存入 7 + 5 = 12

以此类推，搜完倒数第二层，这个三角形会变为

​ 7

​ 3 8

​ 8 1 0

​ 7 12 10 10

4 5 2 6 5

剩下3层也如此类推，最顶层很明显就是正解了

然而这么简单的题我用了两晚上时间来理解orz(我好菜啊)