老年人康复训练：动态规划

• Shader着实看不动了，看多了那Blinn模型脑子里都是布灵布灵的，遂来点老生常谈的算法。

• 动态规划主要思想：步骤分解->用上一步的最优解来计算当前步骤的最优解。 第一步的最优解往往和递归到最底层一样会直接给出。 遵从无后效性原则：即之前的改动不会影响到后续的结果。
• 贪心算法和动态规划的详细介绍和区别：传送门
• 技巧： 1、先判断是否为动态规划，其典型特征为计算步骤可以进行划分，且计算内容重复。 2、判断动态规划类型：线型，区间型，棋盘型，树、图上的动态规划等。 3、从1->2到k->k+1确立动态规划方程式
• （尽量会保持递增难度进行题目排列）

目录

• P1216
• P1434

P1216

• 传送门
• 思路：经典入门题目 1、步骤分解：每一层即我们的一个步骤计算 2、递推式确定：如果只有一层那么当前层的最大值即为最优解，如果有两层，那么直接计算出所有可达路径，之后在下一层找出最大值即可。 第一层->第二层 a[2][i] = a[2][i] + max(a[1][i],a[1][i+1]) 第k层->第k+1层 a[k][i] = a[k][i] + max(a[k][i],a[k][i+1]) 3、Tip：这里的层数为从下向上数，也可以从上向下做，但最后要重新遍历数组找最大值。优点是可以只开两个一维数组节省空间。

#include<iostream>
using namespace std;
int a[1010][1010];

int main()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n;i++)
		for(int j = 1 ; j <= i ; j++)
			cin >> a[i][j];
	for(int i = n - 1; i >= 1 ; i--)
		for(int j = 1 ; j <= i ; j++)
			a[i][j] = a[i][j] + max(a[i+1][j],a[i+1][j+1]);
	cout << a[1][1];
}

P1434

• 传送门