三角形 （C语言代码）动态规划vs深度优先搜索

参考代码1:（时间超限，用path数组记录路径的DFS）

#include <stdio.h>
#include <stdlib.h>

int map[100][100];
int visited[100][100];
typedef struct {
    int i;
    int j;
}node;
node path[101];
int pt=0;
int max=-1;
int n;

void dfs(int i,int j)
{
    path[pt].i=i;path[pt].j=j;++pt;
    visited[i][j]=1;
    if(i==n-1)
    {
        int k,sum=0;
        for(k=0;k<pt;k++)
            {sum+=(map[path[k].i][path[k].j]);}
        if(sum>max) max=sum;
        return;
    }

    if(i<n-1&&!visited[i+1][j])
        {dfs(i+1,j);--pt;visited[i+1][j]=0;}

    if(i<n-1&&j<n-1&&!visited[i+1][j+1])
        {dfs(i+1,j+1);--pt;visited[i+1][j+1]=0;}
}

int main()
{
    int t,i,j;
    scanf("%d",&t);
    while(t&&scanf("%d",&n))
    {
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                {scanf("%d",map[i]+j);visited[i][j]=0;}

        dfs(0,0);
        printf("%d\n",max);
        t--;
    }
    return 0;
}

参考代码2：(输出超限（运行时间过长），DFS）

#include <stdio.h>
#include <stdlib.h>

int map[100][100];
int visited[100][100];
int max,sum;
int n;

void dfs(int i,int j)
{
    visited[i][j]=1;
    sum+=map[i][j];
    if(i==n-1)
    {
        if(sum>max) max=sum;
        return;
    }
    if(i<n-1&&!visited[i+1][j])
        {dfs(i+1,j);sum-=map[i+1][j];visited[i+1][j]=0;}

    if(i<n-1&&j<n-1&&!visited[i+1][j+1])
        {dfs(i+1,j+1);sum-=map[i+1][j+1];visited[i+1][j+1]=0;}
    return;
}

int main()
{
    int t,i,j,k=0;
    scanf("%d",&t);
    while(t&&scanf("%d",&n))
    {
        max=-1;sum=0;
        for(i=0;i<n;i++)
            for(j=0;j<=i;j++)
                {scanf("%d",map[i]+j);visited[i][j]=0;}

        dfs(0,0);
        printf("%d\n",max);
        t--;
    }
    return 0;
}

参考代码3：AC（动态规划）

#include <stdio.h>
#include <string.h>

int Max(int a, int b)
{
    return a>b?a:b;
}

int main()
{
    int n,i,j,m;
    int num[105][105]={0};
    int dp[105][105]={0};

    scanf("%d",&n);
    while(n)
    {
        scanf("%d",&m);
        for(i=0; i<m; i++)
            for(j=0; j<=i; j++)
                scanf("%d",&num[i][j]);
        for(j=0;j<m;j++)
            dp[m-1][j]=num[m-1][j];
        for(i=m-2; i>=0; i--)
            for(j=0; j<=i; j++)
                dp[i][j]=Max(dp[i+1][j],dp[i+1][j+1])+num[i][j];

        printf("%d\n",dp[0][0]);
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        n--;
    }
    return 0;
}