动态规划实现数字三角形的数学思想以及C语言代码详细解析

动态规划是一种通过将大问题分解成更小子问题并存储结果以避免重复计算的算法策略。对于数字三角形，我们可以将其视为从上到下，每个数字等于其上方两数之和的问题，这就是经典的“斐波那契数列”问题的变种。动态规划在这个问题中体现在我们创建一个数组或表格，用于保存已经计算过的和，避免每次都重新计算。

以下是使用C语言实现动态规划求解数字三角形最底层元素总和的基本步骤：

#include <stdio.h>

int dp[100][100]; // 数组大小根据实际三角形调整

void solve(int row, int col) {
    if (row == 0 || col == 0 || col > row) return; // 边界情况处理
    if (dp[row][col] != -1) return; // 如果已计算过，直接返回
    dp[row][col] = solve(row - 1, col - 1) + solve(row - 1, col); // 动态转移方程
}

int main() {
    // 初始化dp数组，设置边界位置的值为0，未计算的位置设为-1
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = -1;
        }
    }

    int top_row[] = {1, 2, 3}; // 输入的数字三角形的第一行
    int rows = sizeof(top_row) / sizeof(top_row[0]);

    // 从第二行开始遍历，并递归调用solve()
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = solve(i, j);
        }
    }

    printf("底部数字的和是：%d\n", dp[rows - 1][0]); // 最底层左上角的值就是最终结果
    return 0;
}