数字三角形动态规划c

数字三角形动态规划是一种常见的算法问题，通常用于求解由数字组成的三角形结构的最优路径和。下面是数字三角形动态规划的一般步骤：

1. 定义状态：将数字三角形表示为一个二维数组，假设为dp[][]，其中dp[i][j]表示从顶部到达位置(i, j)的最优路径和。

2. 初始化状态：将顶部的数字赋值给dp，即dp = triangle。

3. 状态转移方程：根据题目要求，从上一行的位置(i-1, j-1)和(i-1, j)可以到达当前位置(i, j)，因此可以得到状态转移方程：
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]，其中triangle[i][j]表示当前位置的数字。

4. 确定边界条件：根据题目要求，最后一行的最优路径和即为所求解，因此可以遍历最后一行的所有位置，找到最小的路径和。

5. 返回结果：返回最后一行中最小路径和即为所求解。

下面是一个示例的C代码实现：

#include <stdio.h>

#define MAX_SIZE 100

int minimumTotal(int triangle[MAX_SIZE][MAX_SIZE], int numRows) {
    int dp[MAX_SIZE][MAX_SIZE];
    
    // 初始化状态
    dp = triangle;
    
    // 状态转移
    for (int i = 1; i < numRows; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            } else if (j == i) {
                dp[i][j] = dp[i-1][j-1] + triangle[i][j];
            } else {
                dp[i][j] = fmin(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    // 确定边界条件
    int minPathSum = dp[numRows-1];
    for (int j = 1; j < numRows; j++) {
        minPathSum = fmin(minPathSum, dp[numRows-1][j]);
    }
    
    return minPathSum;
}

int main() {
    int triangle[MAX_SIZE][MAX_SIZE] = {
        {2},
        {3,4},
        {6,5,7},
        {4,1,8,3}
    };
    int numRows = 4;
    
    int result = minimumTotal(triangle, numRows);
    
    printf("最小路径和为：%d\n", result);
    
    return 0;
}