POJ 3176

==>原题链接

题目概述

最经典的DP，数塔。

思路

DP 或 记忆化搜索 或 从下到上的贪心。

注释的代码为标准DP，未注释部分为记忆化搜索。
记忆化搜TLE了，让小伙伴调了大半天，在此感谢Smile同学。

警示

TLE的原因是初始化ans[]均为0，而int dp()中 >0 才会返回值否则递归搜索，结果全0的数据要全部递归一遍几十个就超时了。
正确的姿势是 初始化为-1，>0 即调用。就不会出这个问题了，因为数字中如果有小于0的会让结果变小，不可能max到。

代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 350 + 10;
int num[N][N];

/*
int dp[N][N];

int main()
{
    int i, j;
    int n, ans = 0;

    freopen("3176.in", "r", stdin);
    memset(dp, 0, sizeof(dp));
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            scanf("%d", &num[i][j]);
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + num[i][j];

            if (dp[i][j] > ans)
            {
                ans = dp[i][j];
            }
        }
    }

    printf("%d\n", ans);


    return 0;
}
*/


int n;
int ans[N][N];

int dp(int i, int j);

int main()
{
    int i, j;
    int res = 0;

    freopen("3176.in", "r", stdin);
    memset(ans, -1, sizeof(ans));
    scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            scanf("%d", &num[i][j]);
        }
    }

    res = dp(1, 1);

    printf("%d\n", res);
    return 0;
}

int dp(int i, int j)
{
    if (i > n)
    {
        return 0;
    }

    if (ans[i][j] >= 0)
    {
        return ans[i][j];
    }

    ans[i][j] = max(dp(i + 1, j), dp(i + 1, j + 1)) + num[i][j];

    return ans[i][j];
}