动态规划
题单介绍
（更多题目可参考[这里](https://www.luogu.com.cn/training/1060#problems)）
在搜索时，我们经常会重复计算一些东西，导致搜索时间过长，超出题目限制。
那我们能不能在算出某些中间结果的时候，先把它记下来。等到下次再需要算它的时候，再把上次记下来的结果拿过来用呢？
先看一下例题[数字三角形](https://www.luogu.com.cn/problem/P1216)
如果使用搜索来做这道题的话，其实很简单。从最高的点开始，每次往左或者往右搜索，直到走到底为止，把路过的点加起来就是这条路的结果。然后从所有路中取最大值即为答案。
代码如下（写法不唯一）：
```cpp
int ans=0,sum=0,n;
int a[100][100];
void dfs(int x,int y){
if(x>n){//如果走过头了
if(sum>ans)//如果当前的和比最大值大，那么更新
ans=sum;
return;
}
sum+=a[x][y];
dfs(x+1,y);//向左走
dfs(x+1,y+1);//向右走
sum-=a[x][y];
}
```
那么如果这道题的行数为100的话，就要执行$2^{100}$次指令。很显然会超时。
我们很轻易的能发现，从起点开始，先向左再向右或先向右再向左，会走到同一个点。而且从这个点开始走，所选的方案跟之前怎么走毫无关系（无后效性）。
那么我就可以先算出这个点走到底部的最优解，再算出起点到这个点的最优解。那么这个点下面的路就不会重复计算了。这样就大大降低了时间复杂度。
```cpp
int dp[100][100];
int dfs(int x,int y){
if(x>n)return 0;
if(dp[x][y])return dp[x][y];//如果被算过了，那么就直接返回结果
dp[x][y]=max(a[x][y]+dfs(x+1,y),a[x][y]+dfs(x+1,y+1));//求出往两边走的最大值，并把结果记录到数组里
return dp[x][y];
}
```
或者，可以写成循环的形式：
```cpp
for(int i=n;i>=1;i--){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];
}
}
```
怎样的题目可以使用动态规划算法呢？
* 题目分为若干步决策
* 能把中间结果用若干个参数来表示并存储的，并且最优解的局部方案也是局部的最优解（最优子结构）
* 前面的选择对后面的选择没有影响的（无后效性）
那么一个题目应该怎么使用动态规划算法解决呢？
* 首先，找到问题的子问题，即怎么用若干参数来表示一个更小的问题。因为经过一步决策之后，问题就变得更小了。（定义状态）
* 推导出状态之间如何转移（状态转移方程式）
* 写出初始条件（最小的状态），并且从最小的子问题一步一步慢慢推出更大的子问题的解，最后推出原问题的解。
* 保证在计算每个子问题时，他所需要用到的子问题都已经得出结果了。