數字三角形問題SDUT————簡單dp

連結

#include<stdio.h>
long dp[110][110];
int n;
void input()
{
    int i, j;
    for(i = 1; i<=n; i++)
    {
        for(j = 1; j <= i; j++)
        {
            scanf("%ld", &dp[i][j]);
        }
    }
}
long Max(long x, long y)
{
    if(x > y) return x;
    else return y;
}
void DP()
{
    int i, j;
    for(i = n; i>= 1; i--)
    {
        for(j = 1; j <= i; j++)
        {
            if(i == n)dp[i][j] = dp[i][j];//其實這一步沒用隻是用于了解
            else
            {
                dp[i][j]+= Max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
    }
}
int main()
{


    scanf("%d", &n);
    input();
    DP();
    printf("%ld", dp[1][1]);
    return 0;
}