数字三角形——dp入门算法

例题：数字三角形
拓展题

题目：

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。

每一步只能由当前位置向左下或右下。

输入格式

第一行包含整数n，表示数字三角形的层数。
接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式
输出一个整数，表示最大的路径数字和。

数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：
30

解析：
dp算法的重点在于：要知道他是怎么样的状态，并且是怎么样从前面那个转移过来的，个人看法是可以理解为从上一步到当前步我应该做些什么，dp算法难度在于思维。

题目分析：
	dp[i][j]表示从（1，1）这个起点开始，到（i，j）的最大和。
	这个题目应该属于dp算法入门题，可以从样例看出和题目看出，从第二行开始，每一个位置加上的数，只会是它正上方的数或者右上方的数。
	因此转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+w[i][j]。这里的意思是上方和右上方的数比较取最大一个加到本事。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+7,inf=0x3f3f3f3f;
int w[N][N],dp[N][N];//dp存放的是从起点到当前位置最大和，w是权值
int main(){
    int n,t;
    cin>>t;
    while(t--){
        memset(dp,-inf,sizeof dp);//开始给全部的和极大负值，方便后面处理
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                cin>>w[i][j];
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(i==1&&j==1)dp[i][j]=w[i][j];//第一个起点不用处理，最大和就是本身
                else{//如果之前不给dp全部赋值为极大负值，如果当前值为赋值，就会和越界点（权值为0）的比较，肯定会选择0导致最后错误
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+w[i][j];//状态转移
                }
            }
        }
        int ans=-1e9;
        for(int i=1;i<=n;i++)ans=max(ans,dp[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}

这个算法还可以进行空间优化，不是重点，不进行解析自行了解即可。

//上面的代码至上而下，这个空间优化代码至下而上，自行了解
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int>Pall;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
const int N=507,INF=0x3f3f3f3f;
int a[N][N],dp[N];
int main(){
    int n,t;
    cin>>t;
    while(t--){
        cin>>n;
        memset(a,-INF,sizeof a);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                cin>>a[i][j];
                dp[j]=a[i][j];
            }
        }
        for(int i=n-1;i>=1;i--){
            for(int j=1;j<=i;j++){
                dp[j]=max(dp[j],dp[j+1])+a[i][j];
            }
        }
        cout<<dp[1]<<endl;
    }
    return 0;
}