前言

在开学前，我一时兴起，想重拾我在一年或两年前学习的c++,就学习了动态规划。不知不觉距离开学已过了三周，我没有过多练习动态规划，想来写一篇动态规划的学习回顾，算是复习了，也希望为其他人提供一些学习的思路吧。（本人水平并不高，如果文章中有错误，请多多包涵）（感谢b站上的老师和教程，我也是从其他大佬的视频中学来的）

正文

在我看来，动态规划就是通过对题目的分析，来得出此状态和前一个状态（或前多个状态）的联系，从而优化代码的复杂度。

例一：跳台阶

我们从一个例子开始讲起。
这里有十级台阶，从第一阶开始走，每次可以走1或2级台阶，问有几种走法。
这个题目中，人的状态有十种，分别是在“第十阶”、“第九阶”、“第八阶”等等，我们可以将他们标注为dp[10]、dp[9]、dp[8]等等。我们直接对dp[10]的情况进行分析，第十阶仅能由第九阶爬一步和第八阶爬两步两种情况爬上来，所以爬到第十阶台阶的方法数dp[10]是爬到第九阶方法数dp[9]和爬到第八阶方法数dp[8]的和，也就可以表示为dp[10] = dp[9] + dp[8]。
以此类推，我们可以对第n级台阶的情况进行分析，第n级台阶仅能由第(n-1)级台阶和第(n-2)级台阶爬上来，可以得出的表达式为dp[x] = dp[x-1] + dp[x-2],这就是我上文所提到的此状态和前一个状态（或前多个状态）的联系，这个联系可以由个体推到整体，也可以直接通过分析题目来得出。
下面是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;

int dp[1005];//开全局数组

int main(){
   int n; cin>>n; //本题中n=10
   dp[1] = 1; dp[2] = 2;//初始化，简单的自己先算，给基础
   for(int i=3;i<=n;i++){
      dp[i] = dp[i-1] + dp[i-2];//公式
   }
   cout<<dp[n];//输出答案
   return 0;
}

例二：背包问题

背包问题例题，对于每个物品来说，都有放或者不放两种情况，我们只需要判断是放入使价值最大还是不放入使价值最大。

代码分析

话不多说，直接上AC代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

int dp[1005][105]; //开二维数组，第一个是背包的容量，第二个是物品的个数
int use[105], value[105];
int main() {
	int t, m; scanf("%d%d", &t, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &use[i], &value[i]);
	}
	for (int j = 1; j <= m; j++) { //推荐先遍历物品，再遍历容量
		for (int i = 1; i <= t; i++) {
			dp[i][j] = dp[i][j-1]; //默认不放，使每个状态都带上值，便于输出
			if (use[j] <= i) dp[i][j] = max(dp[i][j-1], dp[i - use[j]][j - 1] + value[j]); //对比不放和放
		}
	}
	printf("%d", dp[t][m]);
	return 0;
}