dp练习（0）——数字三角形

3298: 数字三角形

时间限制: 1 Sec  内存限制: 128 MB
提交: 114  解决: 29
[提交][状态][讨论版]

题目描述

如图示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路
径，使该路径所经过的数字的总和最大。
●每一步可沿左斜线向下或右斜线向下走；
●1＜三角形行数≤100；

●三角形中的数字为整数0，1，…99；

输入

文件中首先读到的是三角形的行数。

接下来描述整个三角形

输出

最大总和（整数）

样例输入

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

样例输出

30

提示

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
    int n;
    while(cin >> n)
    {
        int a[][];
        memset(a,, sizeof(a));
        for(int i=;i < n;i++)
        {
            for(int j=;j <= i;j++)
                cin >> a[i][j];
        }
        int b[][];
        memset(b,, sizeof(b));
        b[][] = a[][];
        for(int i=;i < n-;i++)
        {
            for(int j=;j <= i;j++)
            {
                b[i+][j] = max(b[i][j]+a[i+][j],b[i+][j]);
                b[i+][j+] = max(b[i][j]+a[i+][j+],b[i+][j+]);
            }
        }
//        for(int i=0;i < n;i++)
//        {
//            for(int j=0;j <= i;j++)
//                cout << b[i][j] <<" ";
//            cout << endl;
//        }

        int maxnum = -;
        for(int j=;j < n;j++)
        {
            if(maxnum < b[n-][j])
                maxnum = b[n-][j];
        }
        cout << maxnum << endl;
    }
    return ;
}

厉害！无敌！牛逼的我！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[][];
int n;

int maxsum = -;
void dfs(int x,int y,int sum)
{
    sum += a[x][y];
    if(sum > maxsum)
        maxsum = sum;
    if(x == n)
        return;
    dfs(x+,y,sum);
    dfs(x+,y+,sum);
}
int main()
{
    while(cin >> n)
    {
        maxsum = -;
        memset(a,, sizeof(a));
        for(int i=;i < n;i++)
        {
            for(int j=;j <= i;j++)
            {
                cin >> a[i][j];
            }
        }
        dfs(,,);
        cout << maxsum << endl;
    }
    return ;
}
/**************************************************************
    Problem: 3298
    User: 2016016294
    Language: C++
    Result: 时间超限
****************************************************************/

一开始用dfs时间超限了。。

嘿嘿