求助！！第8个TLE

_Waldeinsamkeit_ @ 2022-09-12 18:16:24

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int a[1010][1010],b[1010][1010]={0},n;
int fi(int x,int y)
{
    if (x==n)
        return a[x][y];
    if (b[x][y]!=0)
        return b[x][y];
    int c,m;
    m=fi(x+1,y);
    c=fi(x+1,y+1);
    b[x][y]=max(c,m)+a[x][y];
    return b[x][y];
}
int main()
{
    int m,i,j;
    cin>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=i;j++)
            cin>>a[i][j];
    int f=1;
    m=fi(1,1);
    cout<<m;
    return 0;
} 

by SugarKite @ 2022-09-25 20:18:39

dfs会超时，用dp就行

by heike305 @ 2022-12-15 20:14:22

不看数据范围，a[x][y]能取到0，

if (b[x][y]!=0)return b[x][y];

应改为

if (b[x][y]!=-1)return b[x][y];

还有

int m,i,j;
cin>>n;

之间加个

memset(b,-1,sizeof(b));

另外，用记忆化搜索能AC

@Tzy090420

@xueshenzhixing

by Fischl322 @ 2023-01-29 21:40:55

我也被这个困扰了好久不过终于想通了，如果一个数据由大量的0组成，由于我们判断是否调用mem数组的依据是mem此时是否为0，那么在算那一堆0的重复部分的时候根本不会调用已经算过的mem数组而是变成了朴素的dfs，所以会超时，所在这里要将记忆化数组初始化为不可能达到的数据比如-1，就不会有这种情况发生

by nanamma @ 2023-03-06 22:11:04

我也是用递归写的，也是8卡住

原因： 数据0太多了

解决方法：

dp储存记录的表要用-1填充

memset(b,-1,sizeof(b));

调用的时候判断

if(b[m][n]>=0) ;//直接赋值
else ;//调用递归并存b[m][n]