动态规划：线性dp、背包问题、区间1

记忆化搜索
将之后可以重复用到的子问题的答案进行记录。典例：斐波那契数列、走楼梯、走蜂窝。
斐波那契改进：走楼梯，第i阶台阶不能走。直接强行让第i级台阶方案数等于0即可。
推广：从起点到终点的最短路径方案数，可以通过广搜标记计算每一个点到达的方案数。

1163 -- The Triangle
图 1 显示了一个数字三角形。编写一个程序，计算从顶部开始到底部某处结束的路线上通过的最大数字总和。每一步都可以对角线向左或向右对角线向下。

从上往下写比较容易想，但从下往上写可以直接在顶点取到答案，数组开的也小，只用存输入数据即可，后面会自动更新。
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f, maxn=105;
int n,f[maxn][maxn];
i

动态规划：线性dp、背包问题、区间1最先出现在Python成神之路。