codevs-p1220-triangle

Problem URL:Number Triangle

Problem Description:

Given a Triangle built up with numbers,you can move between numbers where there is an edge between them.And the weight of a move is the sum of two numbers.Now you need to find a way move from the top to the bottom that the weight is the maximum of all ways.
(The Given picture’s maximum weight is 27-> 7+3+8+7+2)

This is a classic DP problem.Also it is a appropriate DP for elementary learner.

First we need to transform the input data in order to make judging borders easier.So how to transform?
The given triangle is:

          1
        2   3
      4   5   6
    7   8   9  10

And After transform:

    1
    2 3
    4 5 6
    7 8 9 10

Then We can instantly know the transitional function。
The traditional function obviously is:

F[i,j]=max(F[i,j]+F[i-1][j],F[i,j]+F[i-1][j-1]);

Ok,Talk is really cheap.The Source code is below:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int g[110][110];



int main(){
    int n;
    cin>>n;
    memset(g,-100,sizeof(g));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>g[i][j];
        }
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            g[i][j]=max(g[i][j]+g[i-1][j-1],g[i][j]+g[i-1][j]);
        }
    }
    int maxn=-10000;
    for(int i=1;i<=n;i++){
        maxn=max(maxn,g[n][i]);
    }
    cout<<maxn;
    return 0;
}