动态规划——初步动态规划 2022年03月10日 第一弹

对于上面这道题，第一反应应该是：DFS或BFS

但是仔细看数据范围,一百万显然会时间超限

这时，就需要用到动态规划

到第i个数的前一步,是不是有且仅有两条路:i-3和i-2

这里我们建一个数组f,f[i]表示走到i可以获得的最大价值

那对于第i个数，他只能是从i-2和i-3走过来的

那么我如果想要求得f[i]的最大值，是不是就需要得到f[i-2]或者是f[i-3]的最大值

那么f[i]=f[i-2]+a[i]//a[i]表示数列里第i个数

或者是f[i]=f[i-3]+a[i]

那么我有两条路，我想要获得最大值，我是不是就要取上面两条路能获得的最大值

所以最后:

f[i]=max(f[i-2]+a[i],f[i-3]+a[i])

最后只需要遍历1~n的最大值,输出a[n],时间复杂度为O(n),可以通过此题

完整代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int n;
int a[N];
int f[N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	f[1] = a[1];
	for (int i = 3; i <= n; i++) {
		if (i == 3) {
			f[i] = f[i - 2] + a[i]; //特殊处理
		} else {
			f[i] = max(f[i - 2] + a[i], f[i - 3] + a[i]);
		}
	}
	cout << f[n] << endl;
	return 0;
}

再来仔细看下求动态规划的过程

首先，确定了f[i]表示走到i可以获得的最大价值，这就叫做状态，找好状态是做出动态规划的关键，状态一般和题目答案相关，或者就是答案本身，如这道题,f[n]就是答案本身

然后我们找到了和f[i]相关的子问题f[i-2],f[i-3]，这叫做阶段

最终我们确定:f[i]=max(f[i-2]+a[i],f[i-3]+a[i]),这就是决策，本质上叫做状态转移方程，本质上就是推卸责任

使用动态规划必须满足无后效性和最优子结构
在上面这个问题中，f[i]的结果对于f[i-2],f[i-3]没有影响，因为我们是从前往后走的，这就是无后效性

f[i]是最优的，f[i-2]和f[i-3]同样是最优的，这就是最优子结构