C++基础算法：动态规划dp

正如题目所说，动态规划非常基础

动态规划的三个重要元素

1.阶段

2.状态

3.状态转移方程

阶段：

将问题划分成若干个更简单的子问题进行求解，在划分的过程中，需要将问题分成若干份，即阶段

状态：

一般来说，动态规划经常用于求解最值问题，每一个阶段的最值就是这个阶段的问题对应的状态

状态转移方程：

就是递推式，前面说了，动态规划的基本思想是将问题转化为若干个子问题进行求解，如果通过这些子问题得出问题的最值，这个转化的数学公式就是状态转移方程。

动态规划经典问题

1.最长不下降子序列

思路：我们用a存储原数组，dp[i]表示从第1个数到第i个数的最长不下降子序列长度（必须以第i个数结尾），对于第i个数而眼，我们检索i之前的所有数，只要与i构成不下降关系，那么i的最长不下降子序列长度就为1和这个数对应的最长下降子序列长度+1的最大值

状态转移方程：略   dp[i] = max(dp[j] + 1)     1 <= j < i 且 a[j] <= a[i]

代码如下

#include 
#include 
using namespace std;

const int N = 210;
int a[N],dp[N],n,pre[N],maxn,p;
stack  stk;

int main () {
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> a[i];
	for (int i = 1;i <= n;i++) {
		int ans = 0;
		for (int j = 1;j < i;j++) {
			if (a[j] <= a[i] && dp[j] > ans) {
				ans = dp[j];
				pre[i] = j;
			}
		}
		dp[i] = ans + 1;
	//	cout << pre[i] << endl;
	}
	for (int i = 1;i <= n;i++) {
		if (dp[i] > maxn) {
			maxn = dp[i];
			p = i;
		}
	}
	cout << "max=" << maxn << endl;
	while (p) {
		stk.push(a[p]);
		p = pre[p];
	}
	while (stk.size()) {
		cout << stk.top() << " ";
		stk.pop();
	}
	cout << endl;
	return 0;
}