120. Triangle

......[2],

.....[3,4],

....[6,5,7],

.. [4,1,8,3]

经典例题，求从上到下最短。

解决方法:

• DFS: Traverse

• DFS: Divide Conquer

• Divide Conquer + Memorization

• Traditional Dynamic Programming

DFS: Traverse：

min = MIN_VALUE; traverse(triangle, 0, 0, 0);

一个list套list模拟树状结构，对于该树状结构的一个节点(0, 0)来说，它的左右子节点的表达方式：

• 左下：行 + 1，列不变： (1, 0)
• 右下：行 + 1，列 + 1: (1, 1)

min 不能做参数，受java底部引用的限制，这一点前面已经有很多例子了。但是全局变量的写法一直都不是我喜欢的，我觉得应当避免的写法。

public class Solution {
    int min;
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;

        min = Integer.MAX_VALUE;
        traverse(triangle, 0, 0, 0);
        return min;
    }
    private void traverse(List<List<Integer>> triangle, int x, int y, int sum) {
        if (x == triangle.size()) {
            min = Math.min(min, sum);
            return;
        }
        traverse(triangle, x + 1, y, sum + triangle.get(x).get(y));
        traverse(triangle, x + 1, y + 1, sum + triangle.get(x).get(y));
    }
}

显然会超时

时间复杂度是多少呢？无奖竞猜：

• A - O(n)
• B - O(n^2)
• C - O(2^n)
• D - O(n!)

提示：一个树状结构有 n 层，递归要 n 层，每一层有两个选择。

DFS: Divide Conquer

这个和刚才差不多，还是递归.

• 左下：行 + 1，列不变： (x + 1, y)
• 右下：行 + 1，列 + 1: (x + 1, y + 1)

这次很不错，很棒，没有用全局变量，写着就跟普通二叉树遍历没什么太大区别。

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;

        return dfs(triangle, 0, 0);
    }
    private int dfs(List<List<Integer>> triangle, int x, int y) {
        if (x == triangle.size()) {
            return 0; //just like root == null
        }
        int left = dfs(triangle, x + 1, y);
        int right = dfs(triangle, x + 1, y + 1);

        return Math.min(left, right) + triangle.get(x).get(y);
    }
}

显然还是会超时

这次的时间复杂度是多少呢？无奖竞猜：

• A - O(n)
• B - O(n^2)
• C - O(2^n)
• D - O(n!)

Divide Conquer + Memorization

我们来思考一下，前面的方法之所以会超时，是因为我们干了一些没用的事，因为有的点进入了两次。本来已经在别的点的下面算过了右子树，我们跑到另一个点的下面又去了算了一遍左子树，但实际上是同一个节点，我们算了两遍。这显然会超时。

委座又出来了：以空间换时间。

记忆化搜索！记住那些已经计算过的点，加一个hash表。

先要初始化，都变成MAX_VALUE，如果我们到了最后一行，那就返回最后一行的值就行了。因为下面没有了。

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;

        int n = triangle.size();
        int[][] hash = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                hash[i][j] = Integer.MAX_VALUE;
            }
        }
        return dfs(triangle, hash, 0, 0);
    }
    private int dfs(List<List<Integer>> triangle, int[][] hash, int x, int y) {
        if (x == triangle.size() - 1) {
            return triangle.get(x).get(y); // root is leaf
        }
        if (hash[x][y] != Integer.MAX_VALUE) {
            return hash[x][y];
        }
        int left = dfs(triangle, hash, x + 1, y);
        int right = dfs(triangle, hash, x + 1, y + 1);

        hash[x][y] = Math.min(left, right) + triangle.get(x).get(y);
        return hash[x][y];
    }
}

这次不超时了，因为我们优化过了啊。

这次的时间复杂度是多少呢？这次好猜：

• A - O(n)
• B - O(n^2)
• C - O(2^n)
• D - O(n!)

Traditional Dynamic Programming

好，终于到重点了，这题用动规，怎么做？

多重循环方式。上一层依赖于下一层，所以应该 bottom-up。

熟悉的配方：

• 左下：行 + 1，列不变： (x + 1, y)
• 右下：行 + 1，列 + 1: (x + 1, y + 1)

• state: f[i][j] 表示从 i，j 出发走到最后一层的最小路径长度。
• function: f[i][j] = MIN(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
• initialization: f[n - 1][i] = triangle[n - 1][i] 赋最后一层的值，因为我们要 bottom-up
• answer: f[0][0] again, bottom-up

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) return 0;

        int n = triangle.size();
        int[][] f = new int[n][n];

        for (int i = 0; i < n; ++i) {
            f[n - 1][i] = triangle.get(n - 1).get(i);
        }
        for (int i = n - 2; i >= 0; --i) { // from n - 2 level to 0 level
            for (int j = 0; j <= i; ++j) { // from left to right
                f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle.get(i).get(j);
            }
        }
        return f[0][0];
    }
}

时间空间复杂度？

• A - O(n)
• B - O(n^2)
• C - O(2^n)
• D - O(n!)

写了两百行废话终于说完了，我们下面正式进入坐标型动态规划：

坐标型动态规划

• state:

  • f[x] 表示我从起点走到坐标x......

  • f[x][y] 表示我从起点走到坐标x,y......

• function: 研究走到 x, y 这个点之前的一步

• initialize: 起点

• answer: 终点

64. Minimum Path Sum

• state: f[x][y]从起点走到 x, y 的最短路径
• function: f[x][y] = min(f[x - 1][y], f[x][y - 1]) + A[x][y]
• intialize:
  • f[i][0] = sum(0,0 ~ i,0)
  • f[0][i] = sum(0,0 ~ 0,i)
• answer: f[m - 1][n - 1]

只要是初始化二维的动态规划，就要初始化第 0 行，第 0 列。

这么简单一个题，我tm检查一个typo看了20分钟。

public class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int m = grid.length;
        int n = grid[0].length;
        int[][] f = new int[m][n];

        f[0][0] = grid[0][0];

        for (int i = 1; i < m; ++i) {
            f[i][0] = f[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; ++i) {
            f[0][i] = f[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
}

节省空间：

public class Solution {
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        for(int i = 1; i < cols; i++){
            grid[0][i] += grid[0][i - 1];
        }
        for(int i = 1; i < rows; i++){
            grid[i][0] += grid[i - 1][0];
        }

        for(int i = 1; i < rows; i ++){
            for(int j = 1; j < cols; j++){
                grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }

        return grid[rows - 1][cols - 1];
    }
}

62. Unique Paths

• state: f[x][y]从起点到 x, y 的路径数
• function: (研究倒数第一步) f[x][y] = f[x - 1][y] + f[x][y - 1]
• initialize:
  • f[0][i] = 1
  • f[i][0] = 1
• answer: f[m - 1][n - 1]

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];

        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int i = 0; i < n; ++i) {
            f[0][i] = 1;
        }

        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

63. Unique Paths II

有障碍不能走。注意初始化。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) return 0;

        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] f = new int[m][n];

        for (int i = 0; i < m; ++i) {
            if (obstacleGrid[i][0] != 1) {
                f[i][0] = 1;
            } else break;
        }
        for (int i = 0; i < n; ++i) {
            if (obstacleGrid[0][i] != 1) {
                f[0][i] = 1;
            } else break;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[i][j] = 0;
                } else f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

70. Climbing Stairs

我拿去当背包问题的intro了，实际上是所有动规的intro。同时也是最高频动规题，同时还是最简单的动规题吧。

这个要是面试时候写错了就太尬了。

public class Solution {
    public int climbStairs(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;

        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;

        for (int i = 2; i <= n; ++i) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

55. Jump Game

用动规会超时，时间复杂度n^2。小细节容易出错，重点复习。

这道题有点特殊是因为我们返回的就是一个True False，也就是说你跳到最后一步前的起点是不确定的。不一定非要从 i - 1 的位置跳到 i ，所以说你必须每个位置都要考虑，也就是说一个一维数组需要 nested for loop。需要一个 j 来确定起点，看看每一个点是不是都有可能跳到最后，所以导致了n^2的复杂度导致了超时。

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;

        boolean[] f = new boolean[n];
        f[0] = true;

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (f[j] && j + nums[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];
    }
}

这道题最优的解法是贪心法，这也是贪心法为数不多的应用场景，贪心法应用的太少了所以我们都没有一个专门的专题来做。

但是偶尔也能碰见这样的题必须用贪心。

public class Solution {
    public boolean canJump(int[] nums) {
        int max = nums[0];

        for (int i = 0; i < nums.length; ++i) {
            if (i <= max && nums[i] + i >= max) {
                max = nums[i] + i;
            }
        }
        return max >= nums.length - 1;
    }
}

45. Jump Game II

依旧是用动规会超时，时间复杂度n^2。

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;

        int[] f = new int[n];
        f[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            f[i] = Integer.MAX_VALUE;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (f[j] != Integer.MAX_VALUE && j + nums[j] >= i) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[n - 1];
    }
}

贪心：

public class Solution {
    public int jump(int[] nums) {
        int start = 0;
        int end = 0;
        int count = 0;

        while (end < nums.length - 1) {
            int max = end;
            count++;
            for (int i = start; i <= end; ++i) {
                if (nums[i] + i > max) {
                    max = nums[i] + i;
                }
            }
            start = end + 1;
            end = max;
        }
        return count;
    }
}

Jump Game是两道很特别的题，需要多加注意。