目录

前言

题目介绍

输入样例:

输出样例:

引入：

理论存在，实践开始！

 基础数塔（数字三角形问题）

与其类似的本题 

本题注意事项： 

​Love is worth years.热爱可抵岁月漫长。

前言

关于数塔的dp                              

题目介绍

输入样例:

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

输出样例:

4

在开始之前大家可以先自己写一下看一下能不能自己写出来~注意输出的格式哦！

引入：

这想明白不就是从最后向前推的一个数塔嘛？？最后输出dp[0][5]的值不就好了？好了，不就是动态规划   ：》

理论存在，实践开始！

 基础数塔（数字三角形问题）

题目介绍：

 输入样例：

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

 输出样例：

30

#include <stdio.h>
int max (int a,int b);
int max (int a,int b)
{
    if(a>b) return a;
    else return b;
    }
int main()
{
    int n;
    scanf("%d",&n);
    int max_sum[n][n];
    int d[n][n];;
    int i,j;
    for (i=0;i<n;i++)
    {
        for(j=0;j<=i;j++)
        {
            scanf("%d",&d[i][j]);
        }
    }
    for (j=0;j<n;j++)
    {
        max_sum[n-1][j]=d[n-1][j];
    }
    for (i=n-2;i>=0;i--)
        for (j=0;j<i+1;j++)
        {
            max_sum[i][j]=d[i][j]+max(max_sum[i+1][j],max_sum[i+1][j+1]);
        }
    printf("%d",max_sum[0][0]);
}

与其类似的本题 

#include <stdio.h>
#include <string.h>
int max (int a,int b,int c)
{
    int max=a;
    if(b>max)max=b;
    if(c>max)max=c;
    return max;
}
int max_t(int a,int b)
{
    if(a>b)return a;
        else return b;
}
int dp[100010][12];
 int a[100010][12];//行表示时间，列表示馅饼在那个上边。

int main()
{
    int n;
    int x,t;
    int i,j;
    int maxt=0;
     
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        if(n==0)break;
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&x,&t);
            a[t][x]++;
            if(t>maxt)maxt=t;
        }
        for (j=0;j<=10;j++)
            {
                dp[maxt][j]=a[maxt][j];
            }
        for (i=maxt-1;i>=0;i--)
        {
            for (j=0;j<=10;j++)
            {
                if(j==0) dp[i][j]=max_t(dp[i+1][j],dp[i+1][j+1])+a[i][j];
                    else
                dp[i][j]=max(dp[i+1][j],dp[i+1][j+1],dp[i+1][j-1])+a[i][j];
            }
        }
        printf("%d\n",dp[0][5]);
    }
}

本题注意事项： 

1.在每组输入后要重置数组进行memset(dp,0,sizeof(dp)); memset(a,0,sizeof(a));的操作。

2.要考虑j==0的情况可能会导致错误

3.不用考虑右端点因为我们全设置成0了。

4。栈储存会报错-1073741571 (0xC00000FD)也就是数组规定的太大了，可以用全局变量或结构体定义解决

Love is worth years.
热爱可抵岁月漫长。