题目描述

给出了一个数字三角形。

从三角形的顶部到底部有很多条不同的路径。

对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。

此外，向左下走的次数与向右下走的次数相差不能超过 1。

算法分析

这道题和数字三角形很像，自然而然想到用DP来做，关键是如何保证向左下走和向右下走的次数相差不超过1.
这里我选择用三维DP来做:

状态表示 ：f[i][j][k]表示（i,j）向左下走k步的路径最大和
状态计算 : f[i][j][k] = max(f[i+1][j][k-1],f[i+1][j+1][k]) ,其中第一项不一定存在，需要特判

那么我们最后设向左下走x，向右下走y，只要满足
x + y = n-1,|x - y| <= 1即可，从中取最大值即得解

时间复杂度 O(n^3) = 10^6

c代码

#include<stdio.h>

int s[110][110],n;
int f[110][110][110];

int max(int x,int y)
{
    if(x >= y) return x;
    else return y;
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= i;j++) scanf("%d",&s[i][j]);
    }
    for(int i = 1;i <= n;i++) f[n][i][0] = s[n][i];/*在最后一层n，向左下走0步的最大值即为s[n][i]*/
    for(int i = n-1;i >= 1;i--)/*从下面往上遍历，避免边界等问题*/
    {
        for(int j = 1;j <= i;j++)
        {
            for(int k = 0;k <= n - i;k++)
            {
                f[i][j][k] = f[i+1][j+1][k] + s[i][j];/*从右下上来*/
                if(k >= 1) f[i][j][k] = max(f[i][j][k],f[i+1][j][k-1] + s[i][j]);
            }
        }
    }
    int res = 0;
    if(n % 2 == 1) printf("%d",f[1][1][(n-1)/2]);/*n-1是偶数，只能是向左下(n-1)/2，向右下()n-1*/2/
    else printf("%d",max(f[1][1][(n-1)/2],f[1][1][(n-1)/2+1]));/*向左下(n-1)/2，或向左下(n-1)/2+1*/
    return 0;
}

有任何问题可以在评论区留言哟，大家一起讨论
如果觉得有帮助就给我点个赞吧！