题目
- 给定一个三角形，从顶到底找到所有路径消耗代价最小的和，每一步你都可以移动该行上相邻的数字
- 举例：给定下图中的三角形
- 从顶部到底部的路径和最小的是11,（2+3+5+1=11）
分析&&解法
- 首先我们先假设这是一个函数f[i][j](1<=i<=n, 1<=j<=i)表示第i行上加上第j个数的最小路径的总和，此时我们的解析应该是用上一行中相邻的最小数加上对应的a[i][j]的值就是我们要求的f[i][j]
- 因此，f[i][j] = min{f[i-1][j],f[i-1][j-1]}+a[i][j]，由此我们得到了整个状态转移的方程，也很显而易见这是一道动态规划解题
- 根据动态规划三要素，我们可知f[n][j] = min{f[n-1][j],f[n-1][j-1]}+a[n][j],其状态转移方程如上中所示
- 边界条件为f[1][1] = a[1]1
- 如果按照这种声明我需要声明一个n^2的数组，空间略大，实际上我只需要一个长度为n的数组就可以表示对应的结果值，我只需要在做状态转移时j的值从大变到小即可以实现，因为j的关系只会涉及到f[i-1][j]和f[i-1][j-1]，此时将f[i][j]计算覆盖到原数组，并不会影响之后的数据计算
- 当最后一行计算完成后采用遍历的方式从f[i][j]中取出最小值就是我们所需要的结果。
- 时间复杂度O(n+n^2 + n) ~O(n^2),空间复杂度O(n)
源代码实现
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
if (triangle == null) return 0;
if (triangle.size() == 1) return triangle.get(0).get(0);
int minTotal = Integer.MAX_VALUE;
int[] aux = new int[triangle.size()];//声明一个辅助数组用于存储f[i][j]的数据
for (int i=0; i<aux.length; i++) aux[i] = Integer.MAX_VALUE;
aux[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
for (int j = triangle.get(i).size()-1; j >= 0; j--) {
if(j != 0) aux[j] = Math.min(aux[j], aux[j-1]) + triangle.get(i).get(j);
else aux[j] = aux[j] + triangle.get(i).get(j);
}
}
for (int i = 0; i < aux.length; i++) minTotal = Math.min(aux[i], minTotal);
return minTotal;
}
}
