leetcode 120 三角形最小路径和

LeetCode 120 三角形最小路径和

• 尝试一: 贪心策略(无法得到全局最优解)
  每层向下在所有可选节点中选择一个值最小的节点
  错误示例: [[1], [2,3], [1,-1,-3]]
  • 贪心结果: 1+2+(-1)=2
  • 正确结果: 1+3+(-3)=1
• 尝试二: DFS搜索(存在超时可能)
  搜索过程存在大量重复
  示例: [[a1], [b1,b2], [c1,c2,c3], [d1,d2,d3,d4]]
  重复搜索有:
  • a1,b1,*c2,(d1 or d2)* a1,b2,*c2,(d1 or d2)*
  • 上述过程对于由c2向底层搜索最优解的子问题存在重复求解
• 尝试三: 记忆化DFS搜索(实质是对递归过程中重复用到的子问题解进行记忆，进而避免对于子问题求解的重复递归调用)
  记忆化数组: 用于保存已有的子问题解，避免对于子问题求解递归过程的重复调用

class Solution {
    Integer[][] memo;      //记忆化数组，memo[i][j]表示由(i,j)处节点向底层搜索的最优结果
    public int minimumTotal(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];      //memo数组存在许多冗余(无效数据位)，可以继续优化
        return  dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        /*若已有(i,j)向下的搜索结果，则直接调用*/
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        /*memo数组的填充过程是一个自下而上的递推过程*/
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }
}

尝试四: 动态规划(实质是将记忆化递归过程转为了一个自下而上的递推过程)

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}