数塔

1258：【例9.2】数字金字塔

分析1：
从顶层到底层，面临n-1次决策。向左还是向下？n-1个决策构成一个从顶到底的路径。共有2^n-1 条路径，我们的任务是从这些路径中选一条，使得经过的数字之和最大。

n-1次决策可以用长度为n-1的01串表示。

我们穷举所有01串，计算每条路径的和，打擂台求最大。

但是当n很大时，穷举次数太多，导致超时。所以我们在不超时的情况下判断尽可能多的01串，以争取得到最大值。

# include <bits/stdc++.h>
/*
5
13
11 8
12 7  26
6  14 15 8
12 7  13 24 11

86
*/

using namespace std;
const int N=1010;
int n,t,s,a[N][N],maxV=0;

void read(){
    cin>>n;
    for (int i=1;i<=n;i++) 
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
}
int find(unsigned long int t){
    int x=1,y=1;
    int s=a[x][y];
    for(int c=1;c<n;c++){
        int fx=t&1;
        x++;y+=fx;
        s+=a[x][y]; 
        //cout<<x<<" "<<y<<" "<<a[x][y]<<endl;
        t=t>>1;
    }
    return s;       
    
}

int main(){
    read();    
    srand(time(nullptr));    
    int T=1000000;
    while(T--){
        unsigned long int t= rand()*rand();//产生一个大的随机数t,用它的2进制值表示一个方案 
        //cout<<t<<endl;
        int m=find(t);
        if(m>maxV) maxV=m;
    }        
   cout<<maxV<<endl;


    return 0;
}

分析2：

用f(1,1) 表示从1，1出发时获得的最大和，

f(1,1)=a[1][1]+max(f(2,1),f(2,2))

f(2,1)=a[2][1]+max(f(3,1),f(3,2))

f(2,2)=a[2][2]+max(f(3,2),f(3,3))

所以一般式为：

f(i,j)=a[i][j]+max(f(i+1,j),f(i+1,j+1))   （i<n）

f(i,j)=a[i][j]   （i=n）

于是我们可以用深搜。

# include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,a[N][N],s[N][N];

void read(){
    cin>>n;
    for (int i=1;i<=n;i++) 
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
}
int find(int x,int y){    
    if(x==n) return a[n][y];        
    int t1=find(x+1,y);
    int t2=find(x+1,y+1);        
    return a[x][y]+max(t1,t2);    
}
int main(){    
    read();        
    cout<<find(1,1)<<endl;
    return 0;
}

分析3：发现有重复计算，譬如：

f(2,1)=a[2][1]+max(f(3,1),f(3,2))    

f(2,2)=a[2][2]+max(f(3,2),f(3,3))

他们都要算 f(3,2)，我们可以记录一下这些值，下次遇到时可以直接调用。

所以我们增加一个数组，记录这些值。这就是记忆化搜索了。这是几乎可以解决n达1000层的问题了。

# include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n,a[N][N],s[N][N];

void read(){
    cin>>n;
    for (int i=1;i<=n;i++) 
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
}

int find(int x,int y){
    if (s[x][y]!=0) return s[x][y];  
    if(x==n) return a[n][y];
    int t1=find(x+1,y);
    int t2=find(x+1,y+1);
    s[x][y]= a[x][y]+t1;
    if(t2>t1) s[x][y]=a[x][y]+t2;
    return s[x][y];    
}

int main(){
    read();        
    cout<<find(1,1)<<endl;
    return 0;
}

分析4：我们可以从底部往上走，把每个小塔的最大和求出来，这个便是DP:

#include<bits/stdc++.h>
using namespace std;
int a[1010][1010];
int n;
int main()
{
   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>0;i--)
     for(int j=1;j<=i;j++)
       a[i][j]+=max(a[i+1][j],a[i+1][j+1]) ;
   
   cout<<a[1][1]; 
    return 0;
}