三角形-题解（C语言+简单图解）

解题思路:

    这是一道较为简单的动态规划题目，明白了其中的思想，解题就很快了。

    首先从一个简单的例子入手，我们先假设一个行数为3的三角形。

    我们从上往下分析，每加入新的一行，它的路径为它的上方和左上方。若要得出可以获得最大值的最佳路径，可将第 i 行第 j 列的数值加上第 i - 1 行的第 j 列与第 j - 1 列元素中的较大值，逐行递推即可。

    但是针对第一列于最后一列的元素而言，一个没有左上方的元素，一个没有上方的元素，所以在实际解题中需要将它们单独提出讨论。

    通过上述的思路，我们对这个简单的例子进行分析：

    对于第二行的元素而言，仅能加上第一行的元素的值，从而得到：

    对于第三行的元素，第一列与最后一列的元素路径被固定，第二列的元素有了讨论的空间。仅需要比较它上方与左上方元素的值的大小即可，将其中的较大者加到第二列的元素上。

    得到从上往下相加的最大值为 10。

    接下来，我们对这个思路进行代码实现。

for(int i = 0; i < n; i ++){
    for(int j = 0; j < i + 1; j ++){
        scanf("%d", &An[i][j]);

        if(i >= 1){
            if(j == 0)            //    当元素为第一列时的情况
                An[i][j] += An[i -1][j];
                
            else if(j == i)       //    当元素处于最后一列的情况
                An[i][j] += An[i - 1][j - 1];
                
            else{                 //    正常情况下可以使用一个三目运算符得到上方与左上方元素的较大值
                int max1 = An[i - 1][j - 1]>An[i - 1][j] ? An[i - 1][j - 1] : An[i - 1][j];
                An[i][j] += max1;
            }
        }
    }
}

    继续运用三目运算符与for循环的结合，得到最后一行元素中的最大值即为答案。

int max = An[n - 1][0];
for(int j = 0; j < n - 1; j ++)
    max = max > An[n - 1][j + 1] ? max : An[n - 1][j + 1];

    这个过程也可以与上方的情况讨论相结合，为了理解与修改方便，还是将其分开。

    最后按照题目要求，在这个for循环的外围再加上一层循环来实现多次分批地输入，便完美完成。

    最后附上完整的代码。

参考代码:

#include int main() {
    int times;
    scanf("%d", &times);

    for(int t = 0; t < times; t ++){
        int n;
        scanf("%d", &n);
        int An[n][n];
        //  ----------------------------------------------
        for(int i = 0; i < n; i ++){
            for(int j = 0; j < i + 1; j ++){
                scanf("%d", &An[i][j]);

                if(i >= 1){
                    if(j == 0)
                        An[i][j] += An[i -1][j];
                    else if(j == i){
                        An[i][j] += An[i - 1][j - 1];
                    }
                    else{
                        int max1 = An[i - 1][j - 1]>An[i - 1][j] ? An[i - 1][j - 1] : An[i - 1][j];
                        An[i][j] += max1;
                    }
                }
            }
        }
        //  ----------------------------------------------
        int max = An[n - 1][0];
        for(int j = 0; j < n - 1; j ++)
            max = max > An[n - 1][j + 1] ? max : An[n - 1][j + 1];
        printf("%d\n", max);
    }
    return 0;
}

    若有改进，欢迎与我讨论٩(˃̶͈̀௰˂̶͈́)و。