120. 三角形最小路径和

题目描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

递归思路

1.既然每次下移都只有两个位置选择，我们完全可以暴力递归所有路径的答案，然后选择最小的即可。
2.每次递归时都需要传入当前行(curRow)、当前行所在索引(rowIndex)以及当前的和(curSum)，递归出口设置为最后一层。

Java代码实现(暴力递归)

  public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0)
            return 0;
        int res = minimumTotal(triangle,0,0,0);
        return res;
    }

    private int minimumTotal(List<List<Integer>> triangle,int curRow,int rowIndex,int curSum) {
        if(curRow == triangle.size()-1)
            return curSum+triangle.get(curRow).get(rowIndex);
        else{
            int c1 = minimumTotal(triangle,curRow+1,rowIndex,curSum+triangle.get(curRow).get(rowIndex));
            int c2 = minimumTotal(triangle,curRow+1,rowIndex+1,curSum+triangle.get(curRow).get(rowIndex));
            return Math.min(c1,c2);
        }
    }

动态规划思路

1.通过上面的递归，我们可以找到状态转移方程，即dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])+dp[i][j];
2.可以声明一个dp数组用于存放结果集，将n-1行，也就是底部赋值后，从n-2行按照状态转移方程迭代求解。
3.最后返回dp[0][0]作为结果即可。

Java代码实现(动态规划)

  public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0)
            return 0;
        int[][] dp = new int[triangle.size()][triangle.size()];

        for (int i = triangle.size()-1; i >= 0 ; i--) {
            dp[triangle.size()-1][i] = triangle.get(triangle.size()-1).get(i);
        }

        for (int i = triangle.size()-2; i >=0 ; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }

        return dp[0][0];
    }