1300 数字金字塔 题解

红小豆

迭代的是人，递归的是神
题目传送门
考虑递归+记忆化
边界条件：层数 = n
记忆化的无用数据：0
状态方程：max(f(x + 1,y),f(x + 1,y)) + a[x][y]

1. #include <iostream>
   
2. using namespace std;
   
3. int a[1005][1005],n,b[1005][1005];
   
4. int f(int x,int y){
   
5.         if (b[x][y] != 0) return b[x][y];
   
6.         if (x == n) return a[x][y];
   
7.         return b[x][y] = max(f(x + 1,y),f(x + 1,y + 1)) + a[x][y];
   
8. }
   
9. int main(){
   
10.         cin >> n;
    
11.         for (int i = 1;i <= n;i++){
    
12.                 for (int j = 1;j <= i;j++){
    
13.                         cin >> a[i][j];
    
14.                 }
    
15.         }
    
16.         cout << f(1,1);
    
17. return 0;
    
18. }

复制代码