题目
三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
示例 1：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
示例 2：
输入：triangle = [[-10]] 输出：-10
提示：
1 <= triangle.length <= 200 triangle[0].length == 1 triangle[i].length == triangle[i - 1].length + 1 -104 <= triangle[i][j] <= 10^4
题解
解题分析
解题思路
- 在本题中，给定的三角形的行数为 n，并且第 i 行（从 00 开始编号）包含了
i+1个数。如果将每一行的左端对齐，那么会形成一个等腰直角三角形，如下所示：
[2] [3,4] [6,5,7] [4,1,8,3]
- 我们使用 f[i][j] 表示从三角形顶部走到位置 (i, j) 的最小路径和。这里的位置 （i，j）指的是三角形中 i 行和 j 列（均从 0 开始） 的位置。由于每一行只能移动到下一行的【相邻的节点】上，因此想要走到位置 （i， j）, 上一步只能在位置 (i-1， j-1) 或者位置 (i -1, j) . 我们在这两个位置中选择一个路径最小的来进行转移。
- 状态转换方程：
f[i][j] = min(f[i-1][j-1], f[i-1][j]) + c[u]
其中 c[i][j] 表示位置 （i, j）对应元素值。
注意：第 i 行上有 i + 1 个元素，他们对应 j 的范围为 [0, i]。 当 j = 0 或者 j = i 时，上述状态转移方程中有些项是没有意义的。例如当 j = 0 时， f[i-1][j-1] 没有意义，因此状态转移方程为：
f[i][0] = f[i-1][0] + c[i][0]
- 即当我们在第 i 行的最左侧时，我们只能从第
i-1行的最左侧移动过来。当j=i时，f[i-1]没有意义，因此状态转移方程为：
f[i][i] = f[i-1][i-1] + c[i][i]
即当我们在第 i 行的最右侧时，我们只能从第 i-1 行的最右侧移动过来。
最终的答案即为 f[n-1][0] 到 f[n-1][n-1] 中的最小值，其中 n 是三角形的行数。
- 注意：状态转移方程的边界条件是什么？由于我们已经去除了所有「没有意义」的状态，因此边界条件可以定为：
f[0][0]=c[0][0]
即在三角形的顶部时，最小路径和就等于对应位置的元素值。这样一来，我们从 1 开始递增地枚举 i，并在 [0, i] 的范围内递增地枚举 j，就可以完成所有状态的计算。
复杂度
时间复杂度： O(N^2)
空间复杂度： O(N^2)
解题代码
题解代码如下（代码中有详细的注释说明, 注意本次选用 C 语言答题）：
int minimumTotal(int** triangle, int triangleSize, int* triangleColSize){ int f[2][triangleSize]; memset(f, 0, sizeof(f)); // 初始化值 f[0][0] = triangle[0][0]; for (int i=1; i < triangleSize; i++) { int curr = i %2; int prev = 1 - curr; f[curr][0] = f[prev][0] + triangle[i][0]; for (int j = 1; j < i; j++) { f[curr][j] = fmin(f[prev][j-1], f[prev][j]) + triangle[i][j]; } f[curr][i] = f[prev][i-1] + triangle[i][i]; } int ret = f[(triangleSize -1) %2] [0]; for (int i =1; i< triangleSize; i++) { ret = fmin(ret, f[(triangleSize - 1) %2][i]); } return ret; }
提交后反馈结果：
