数字三角形算法设计

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

算法设计步骤如下：

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>& triangle) { int n = triangle.size(); vector<vector> f(n, vector(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;