动态规划

基础

是什么

这是解决多阶段决策过程最优化问题的一种方法 (最优化原则).

条件

1. 阶段

a) 将问题的全过程恰当地分成若干个相互联系的阶段,以便按一定的次序去求解.

b) 一般是按时间和空间的自然特征决定的,这样便于把问题转化成多阶段决策的过程.

2. 状态

a) 事物某一阶段的性质.

b) 用一个变量描述.

c) 各状态之间是可以互相转化的.

d) 记录的过程就是一种状态.

3. 决策

a) 是对问题的处理做出某种选择性的行动

b) 一个问题可能要有多种决策,每一个阶段都有一次决策

c) 决策的取值限制在了题目范围中,这个范围称为允许决策集合.

d) 找到动态规划转移方程 (关系).

要素

① 状态表达

② 动态规划转移方程

③ 终止条件

应用

这是配合二位数组的记忆化搜索的.

在记忆化搜索上多了一个最优解的筛选过程*(排除无效的分支,保留最优的分支)*.

解决过程

① 划分阶段

② 确定状态与状态变量*(记录数组)*

③ 确定决策

④ 寻找终止条件

⑤ 编写程序

模板

	for (int i = 2; i <= n; i++)
	{
		for (int k = 1; k < i; k++)
		{
			h[i][k] = max(h[i - 1][k - 1], h[i - 1][k]/*别忘了使用h比较,因为h是记录最大的累加的*/) + a[i][k]; //答案有点类似于滚雪球,层层累加.
			//cout << setw(3) << h[i][k];
		}
		//cout << endl;
	}

例子

具体例子见P1219.cpp.