CZYZ Day-1

比赛第一题错的实在不应该，第二题暴力打了30，第三题广搜比较简单，最后一题看出是dp了，但不会打:sweat:

对动归，有了新的收获，发现它本质上相当于将递推、深搜融为一体，并将其进行简化，找转移方程是解决dp问题的重要步骤
如数字三角形

如下所示为一个数字三角形：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
　● 每一步可沿直线向下或右斜线向下走；
　● 1＜三角形行数≤100；
　● 三角形中的数字为整数0，1，……，99；

这是以前的代码,用的dfs

#include<bits/stdc++.h>
using namespace std;
int mp[105][105],mx;
int n;
void dep(int x,int y,int ans){
    ans+=mp[x][y];
    if(x==n){
        if(ans>mx)mx=ans;
        return;
    }
    dep(x+1,y,ans);
    dep(x+1,y+1,ans);
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)cin>>mp[i][j];
    }
    dep(1,1,0);
    cout<<"max="<<mx;
    return 0;
}

经过dp优化后

```cpp
#include
int n;
int mp[1005][1005],f[1005][1005];
int main(){
    std::cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j>mp[i][j];

for(int i=n-1;i&gt;=1;i--){
    for(int j=1;j&lt;=i;j++){
        f[i][j]=mp[i][j]+std::max(mp[i+1][j+1],mp[i+1][j]);
        mp[i][j]=f[i][j];
    }
}

std::cout&lt;&lt;f[1][1];
return 0;

}
从下向上递推明显时间复杂度优化了不少，由O（2^n）优化为O（n^2）