120. 三角形最小路径和

我所知的最大乐趣是，暗中行善举，但又偶然间为人所知。

题目

参考120. 三角形最小路径和。

解题思路

总体思路其实有两种，一种是自底向上（当前位置路径由上面两个位置的最小路径决定），一种是自顶向下（当前位置的最小路径由下面两个位置的最小路径决定）。自顶向下的代码逻辑更简洁简单一点，但是转移方程都差不多是一样的。

• 递归+记忆化搜索：给出两种思路的代码参考。
• 动态规划+优化空间：给出两种思路的代码参考，并给出空间优化后的代码。

递归+记忆化搜索

自底向上 1ms

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int ans = Integer.MAX_VALUE, n = triangle.size();
        //dp[i][j] 表示 i 行 j 位置的最小路径
        List<Integer> end = triangle.get(n-1);
        //记忆化搜索优化
        int[][] memo = new int[n][n];
        for(int i = 0; i < n; i++) Arrays.fill(memo[i],Integer.MAX_VALUE);
        for(int i = 0; i < end.size(); i++) {
            ans = Math.min(ans,dp(n-1,i,triangle,memo));
        }
        return ans;
    }
    //转移方程 dp[i][j] = min(dp(i-1,j-1),dp(i-1,j)) + triangle[i][j]
    int dp(int i, int j, List<List<Integer>> triangle, int[][] memo) {
        //递归结束条件
        if(i == 0 && j == 0) return triangle.get(i).get(j);
        if(i < 0 || j < 0 ) return Integer.MAX_VALUE/2;
        if(j >= triangle.get(i).size()) return Integer.MAX_VALUE/2;
        //递归
        if(memo[i][j] != Integer.MAX_VALUE) return memo[i][j];
        return memo[i][j] = Math.min(dp(i-1,j-1,triangle,memo),dp(i-1,j,triangle,memo)) 
            + triangle.get(i).get(j);
    }
}

自顶向下 1ms

class Solution {
    Integer[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return  dfs(triangle, 0, 0);
    }

    int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) return 0;
        if (memo[i][j] != null) return memo[i][j];
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) 
            + triangle.get(i).get(j);
    }
}

动态规划+优化空间

自底向上 3ms

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int ans = Integer.MAX_VALUE, n = triangle.size();
        //dp[i][j] 表示 i 行 j 位置的最小路径
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        //转移方程 dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);
        for(int i = 1; i < n; i++) {
            List<Integer> t = triangle.get(i);
            dp[i][0] = dp[i-1][0] + t.get(0);
            dp[i-1][i] = Integer.MAX_VALUE;
            for(int j = 1; j < t.size(); j++) {
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + t.get(j);
            }
        }
        List<Integer> end = triangle.get(n-1);
        for(int i = 0; i < end.size(); i++) {//求最小值
            ans = Math.min(ans,dp[n-1][i]);
        }
        return ans;
    }
}

自顶向下 3ms

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //dp[i][j] 表示 i 行 j 位置开始的最小路径 
        int[][] dp = new int[n+1][n+1];
        //转移方程从上到下 dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
        //则从下到上倒序求值
        for(int i = n-1; i >= 0; i--) {
            List<Integer> t = triangle.get(i);
            for(int j = 0; j < t.size(); j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + t.get(j);
            }
        }
        return dp[0][0];
    }
}

优化空间 3ms

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        //dp[i] 表示 i 位置开始的最小路径 
        int[] dp = new int[n+1];
        //转移方程从上到下 dp[j] = Math.min(dp[j],dp[j+1]) + triangle.get(i).get(j);
        for(int i = n-1; i >= 0; i--) {
            List<Integer> t = triangle.get(i);
            for(int j = 0; j < t.size(); j++) {
                dp[j] = Math.min(dp[j],dp[j+1]) + t.get(j);
            }
        }
        return dp[0];
    }
}

复杂度分析

• 时间复杂度：O(n^2)，双重循环遍历。
• 空间复杂度：O(n^2)或O(n)。