数字三角形最小路径和算法设计与实现

数字三角形是一个由数字组成的三角形，其中每个数字是从上面相邻两个数字中选择的最小值。设计一个算法，给定一个数字三角形，计算从顶部到底部的最小路径和。

算法设计步骤如下：

1. 定义状态：设状态f[i][j]表示从数字三角形顶部到(i, j)位置的最小路径和。

2. 状态转移方程：由于每个数字只能从上面相邻的两个数字中选择最小值，所以状态转移方程为：

f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j]

其中triangle[i][j]表示数字三角形第i行第j列的数字。

3. 边界条件：最顶部的状态为f[1][1] = triangle[1][1]，最底部的最小路径和为min(f[n][j])，其中n为数字三角形的行数，j为最底部一行的任意一列。

4. 求解最小路径和：根据状态转移方程，从顶部开始逐行计算状态，最终得到最小路径和。

代码实现如下：

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> f(n, vector<int>(n, 0));
    f[0][0] = triangle[0][0];
    for (int i = 1; i < n; i++) {
        f[i][0] = f[i-1][0] + triangle[i][0];
        for (int j = 1; j < i; j++) {
            f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j];
        }
        f[i][i] = f[i-1][i-1] + triangle[i][i];
    }
    int ans = f[n-1][0];
    for (int j = 1; j < n; j++) {
        ans = min(ans, f[n-1][j]);
    }
    return ans;
}