蓝桥杯三角型问题动态规划解法c++

解题思路:         问题的解析：关于求最大值问题也就是求最优值问题，不可以采用贪心算法，贪心算法只能得到局部最优

                                                现在开始对问题本身进行分析，这类问题可以从算法设计于分析一书中动态规划一章的求最短海岛路径类推。

                                                先考虑使用回溯法，会发现时间复杂度大概为O(n!),必然发生超时现象。

                                                而当我们从三级性最后一层逐步返回最大值时时间复杂度为0(n^2)是满足测评通过的。

                                                一下是代码实列：

  注意事项:

参考代码:#include<iostream>
using namespace std;
int num[100][100]={0};//本题中因为三角形最大为100层。
int main()
{
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int N;
        cin>>N;
        for(int j=0;j<N;j++)
        for(int k=0;k<=j;k++)//三角型的输入
        {
            int t;
            cin>>t;
            num[j][k]=t;
        }
        for(int j=N-1;j>0;j--)
        {
            for(int k=0;k<j;k++)//从最低层开始返回
            {
                if(num[j][k]<num[j][k+1])//比较左右两边将最大的一个返回至上一层。
                num[j-1][k]+=num[j][k+1];
                else
                num[j-1][k]+=num[j][k];
            }
        }
        cout<<num[0][0]<<endl;//最后第一个数就是最大的值，该算法缺点是会将三角形中除最后一层所有的值都发生了改变。
    }
 }