[动态规划]数字三角形(版本I-III)

level 1

1.1题目

1.1.1题目描述

考虑在下面被显示的数字金字塔。 写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。每一步可以走到左下方的点也可以到达右下方的点。



在上面的样例中,从7 到 3 到 8 到 7 到 5 的路径产生了最大和:30

1.1.2输入

第1行：1个整数R(1<= R<=1000)，表示行的数目。

接下来共R行，第i行有i个整数。所有的数均非负的且不大于100。

1.1.3输出

第1行：可以得到的最大的和。

1.1.4样例输入

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

1.1.5样例输出

30

1.1.6提示

这种题都要给你提示？

1.2分析

一道水的不能再水的 DP基础题…但是这么简单的题还是难道了蒟蒻的我…

1.2.1超时的搜索

嗯…是的,做这道题的时候我还不知道有DP这种东西…于是上场直接搜索:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,maxx,a[1005][1005];
void dfs(int x,int y,int sum)
{
    if(x>n){maxx=max(maxx,sum);return ;}
    dfs(x+1,y,sum+a[x][y]);
    dfs(x+1,y+1,sum+a[x][y]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)scanf("%d",&a[i][j]);
    dfs(1,1,0);
    printf("%d",maxx);
}

然后…

于是瞬间蒙蔽…

1.2.2DP大法出现

两个月后~~

听说这题是用DP才能过的，于是马上自学了部分DP知识，瞬间懂了…

我们可以设f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]为顶向上到此点的最大值，可以列出转移方程

f[i][j]=max(f[i−1][j],f[i−1][j−1])" role="presentation" style="position: relative;">f[i][j]=max(f[i−1][j],f[i−1][j−1])f[i][j]=max(f[i−1][j],f[i−1][j−1])

答案即在f[n][i]" role="presentation" style="position: relative;">f[n][i]f[n][i]中的最大值上.

实现：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[3][1005][1005],maxx,head;
int main()
{
    scanf("%d",&n);
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        scanf("%d",&a[1][i][j]);
    a[2][1][1]=a[1][1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            a[2][i][j]=a[1][i][j]+max(a[2][i-1][j-1],a[2][i-1][j]);
        }
    for(int i=1;i<=n;i++)
    {
        maxx=max(maxx,a[2][n][i]);
    }
    printf("%d",maxx);
    //print(head);
}

level 2

2.1题目

2.1.1题目描述

2.1.2输入

第1行：1个整数N，表示数字三角形的行数和列数(1 <= N <= 1000)

接下来N行，第i行有i个整数，表示数字三角形

2.1.3输出

第1行：1个整数，表示问题的最优解

2.1.4样例输入

5

1

3 6

9 9 1

5 5 2 3

2 9 7 6 1

2.1.5样例输出

30

2.1.5提示

看清楚题就很简单的QAQ

2.2分析

考试的时候看见数字三角形太兴奋以至于没法现题目改了(这数据也太坑了吧233…)

额,貌似多加了一个最多一次走到任意格子上呀…..

其实我们可以再定义一个数组q[i][j]表示使用一次机会从下到上后走到(i,j)时的最大花费,我们定义MAX_NUM为i行f数组的最大值

因此q[i][j]=max(MAX_NUM,max(q[i+1][j],q[i+1][j+1]))

注意,一定是f的最大值,因为需要保证只使用一次机会。

2.3实现

#include<bits/stdc++.h>//作死头文件专场
using namespace std;
int a[1005][1005],n,f[1005][1005],q[1005][1005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            scanf("%d",&a[i][j]);
            f[i][j]=a[i][j];
            q[i][j]=a[i][j];
        }
    for(int i=n-1;i>=1;i--)
    {
        int maxx=0,qx=0;
        for(int j=1;j<=i+1;j++)
        if(maxx<f[i+1][j])
            maxx=f[i+1][j];
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
            q[i][j]=max(maxx,max(q[i+1][j],q[i+1][j+1]))+a[i][j];
        }
    }
    printf("%d",max(f[1][1],q[1][1]));
}

level 3(制作中)

3.1题目

3.1.1题目描述

3.1.2输入

第1行：1个整数N，表示数字三角形的行数和列数(1 <= N <= 1000)

接下来N行，第i行有i个整数，表示数字三角形

3.1.3输出

第1行：1个整数，表示问题的最优解

3.1.4样例输入

5

0

0 1

0 1 0

1 0 0 0

0 0 0 1 0

3.1.5样例输出

3

2.1.6提示

仔细思考一下就能做出来的QAQ

3.2分析

填充中…

3.3代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
bool f[1005][1005][10];
int a[1005][1005],n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        scanf("%d",&a[i][j]),a[i][j]%=10;
    for(int i=1;i<=n;i++)f[n][i][a[n][i]]=1;
    for(int i=n-1;i>=1;i--)
        for(int j=1;j<=i;j++)
            for(int k=0;k<=9;k++)
                if(f[i+1][j][k]||f[i+1][j+1][k])
                    f[i][j][(k+a[i][j])%10]=1;
    int ans=0;
    for(int i=9;i>=0;i--)if(f[1][1][i]){ans=i;break;}
    printf("%d",ans);
}