题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

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

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500,
−10000≤三角形中的整数≤10000

输入样例

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

输出样例：

30

算法1

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

1                                       F(1)

2                   F(1)+F(2)                           F(1)+F(3)

3       F(1)+F(2)+F(4)      F(1)+F(2)+F(5)||F(1)+F(3)+F(5)     F(1)+F(3)+F(6)

由上表我们很容易看出这个很像二叉树,只不过两个父亲有一个孩子（听起来好奇怪）

回到正题,因此我们发现划分成子问题就是在每一层的子节点选择值更大的父亲（选个好爹），
因此根据当前层跟下一层的递推关系，num[i][j] = max(num[i-1][j-1],num[i-1][j]);(i>0)
有这样一个递推关系式，原本全排列优化到了O（n）
就是一个典型的贪心，局部最优
同时因为结果只跟相邻两层有关系所以空间上也可以优化成最大根节点的个数
空间也优化到了n

时间复杂度O(n)

C++ 代码

#include <iostream>
#include <cstdio>
using namespace std;
int num[51];
int read(){
    char c = getchar();
    int num = 0;
    bool negative = 0;
    while(c<'0'||c>'9'){
        if(c=='-')
            negative = 1;
        c =getchar();
    }
    for(;c>='0'&&c<='9';c = getchar()){
        num*=10;
        num+=(c-'0');
    }
    return negative?-num:num;
}
int main(){
    short n = read(),sum[3],&i = sum[0],&j = sum[1],&num2 = sum[2];
    int max,num1;
    for(i = 1;i<=n;i++){
        for(j = 0;j<i;j++){

            num2 = read();//指向i行j元素
            if(j == i-1){
               max=num1;
            }else if(j){
                max = num1>num[j]?num1:num[j];

            }
            else{
                num1 = num[j];
                max = num[j];
            }

            num1 = num[j];
            num[j] = (num2+max);
        }
    }
    num1 = 0;
    for(i = 1 ;i<n;i++){
        if(num[num1]<num[i]){
            num1 = i;
        }
    }
    cout<<num[num1]<<endl;
    return 0;
}