符号三角形回溯算法c语言代码加解题思路附带输入输出

以下是符号三角形回溯算法的C语言代码，附带输入输出和解题思路。

#include <stdio.h>

#define MAX_N 15

int N; // 三角形边长
char triangle[MAX_N][MAX_N + 1]; // 存储三角形

// 求解符号三角形最大值
int dfs(int i, int j, int sum) {
    if (i == N) { // 到达三角形底部，返回和
        return sum;
    }
    // 往下走，选择左边或右边
    int left = dfs(i + 1, j, sum + triangle[i][j]);
    int right = dfs(i + 1, j + 1, sum + triangle[i][j]);
    // 返回左右两边的最大值
    return left > right ? left : right;
}

int main() {
    // 读入三角形
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%s", triangle[i]);
    }
    // 求解符号三角形最大值并输出
    printf("%d\n", dfs(0, 0, 0));
    return 0;
}

输入格式：

第一行包含一个整数N，表示三角形的边长。

接下来N行，每行包含一个长度为1到N+1的字符串，表示三角形。

输出格式：

一个整数，表示符号三角形的最大值。

解题思路：

符号三角形是一个类似于数塔的问题，只不过塔上的数字变成了符号。我们可以用类似于数塔的递归算法来求解。

假设我们正在处理第i行第j列的符号，当前已经得到的和为sum。我们可以往下走，选择左边或右边，分别得到左边的最大值left和右边的最大值right。那么当前符号的最大值就是sum加上左右两边的最大值的较大值。

最后，当我们到达三角形的底部时，直接返回sum即可。

完整代码附带了输入输出，可以直接运行。