三角矩阵(Triangle)
难度：Medium
备注：出自leetcode
题目描述
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent
numbers on the row below.
For example, given the following triangle
[[2],[3,4],[6,5,7],
[4,1,8,3]
]The minimum path sum from top to bottom is11(i.e., 2 + 3 + 5 + 1 = 11).
int minimumTotal(vector &triangle)
来源：牛客-leetcode
来源：力扣：120 三角形最小路径和
题目描述：
给定一个三角矩阵，找出自顶向下的最短路径和，每一步可以移动到下一行的相邻数字。
比如给定下面一个三角矩阵，自顶向下的最短路径和为11。
- 方法：动态规划
- 状态：
子状态：从(0,0)到(1,0),(1,1),(2,0),…(n,n)的最短路径和
F(i,j): 从(0,0)到(i,j)的最短路径和 - 状态递推：
F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j] - 初始值：
F(0,0) = triangle[0][0] - 返回结果：
min(F(n-1, i))
代码：
import java.util.ArrayList;/*** 方法：动态规划* 状态：* 子状态：从(0,0)到(1,0),(1,1),(2,0),...(n,n)的最短路径和* F(i,j): 从(0,0)到(i,j)的最短路径和* 状态递推：* F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]* 初始值：* F(0,0) = triangle[0][0]* 返回结果：* min(F(n-1, i))* 最后一行最小的元素*/public class Solution {public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {if (triangle == null) return 0;ArrayList<ArrayList<Integer>> result = new ArrayList<>();int row = triangle.size();for (int i = 0; i < row; i++) {result.add(new ArrayList<>());}// F[0][0]初始化result.get(0).add(triangle.get(0).get(0));for (int i = 1; i < row; i++) {//上一行的最小值int curSum = 0;for (int j = 0; j < triangle.get(i).size(); j++) {// 处理左边界和右边界if (j == 0) {curSum = result.get(i - 1).get(0);} else if (j == i) {curSum = result.get(i - 1).get(j - 1);} else {curSum = Math.min(result.get(i - 1).get(j - 1), result.get(i - 1).get(j));}// F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]result.get(i).add(curSum + triangle.get(i).get(j));}}int size = triangle.size();// min(F(n-1, i))int allMin = result.get(size - 1).get(0);//在最后一行找最小的值for (int i = 1; i < result.get(size - 1).size(); i++) {allMin = Math.min(result.get(size - 1).get(i), allMin);}return allMin;}
}