动态规划

题目分类

矩阵型DP

Unique Paths II : 矩阵型DP，求所有方法总数
Minimum Path Sum:矩阵型，求最大最小值
Triangle : 矩阵型，求最大最小值
Maximum Square ：矩阵型，求最大最小值
Range Sum Query 2D - Immutable : 求和

Unique Paths II : 矩阵型DP，求所有方法总数

方法一：自顶向下

递归法,time limited

class Solution {

    int helper(int[][] g, int x, int y){

        int top = 0, left = 0;

        if(g[x][y] == 1) return 0;

        if(x == 0 && y == 0) return 1;

        if(x > 0){

            top = helper(g, x - 1, y);

        }

        if(y > 0){

            left = helper(g, x, y - 1);

        }

        return top + left;

    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        return helper(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length -1);

    }

}

方法一：自顶向下

递归法 + memo ac

class Solution {

    Map<Long, Integer> m = new HashMap<>();

    int helper(int[][] g, int x, int y){

        int top = 0, left = 0;

        if(g[x][y] == 1) return 0;

        if(x == 0 && y == 0) return 1;

        long key = ((long)x) << 32 | y; // long key = x << 32 | y; 错误

        if(m.containsKey(key)) return m.get(key);

        if(x > 0){

            top = helper(g, x - 1, y);

        }

        if(y > 0){

            left = helper(g, x, y - 1);

        }

        m.put(key, top + left);

        return top + left;

    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        return helper(obstacleGrid, obstacleGrid.length - 1, obstacleGrid[0].length -1);

    }

}

方法三：自底向上

递推 + memo

这里用了二维memo，其实状态转移中，当前step只与上一step有关系，只用一维memo就可以了。

class Solution {

    public int uniquePathsWithObstacles(int[][] g) {

        if(g.length == 0) return 0;

        int[][] ps = new int[g.length][g[0].length];

        boolean obstacle = false;

        for(int i = 0; i < g.length; i ++){

            if(g[i][0] == 1){

                obstacle = true;

            }

            ps[i][0] = obstacle ? 0 : 1;

        }

        obstacle = false;

        for(int i = 0; i < g[0].length; i ++){

            if(g[0][i] == 1){

                obstacle = true;

            }

            ps[0][i] = obstacle ? 0 : 1;

        }        

        for(int i = 1; i < g.length; i++){

            for(int j = 1; j < g[0].length; j++){

                if(g[i][j] == 1){

                    ps[i][j] = 0;

                }

                else{

                    ps[i][j] = ps[i-1][j] + ps[i][j-1];

                }

            }

        }

        return ps[g.length-1][g[0].length-1];

    }

}

Minimum Path Sum:矩阵型，求最大最小值

方法一：自底向上 + 二维memo

class Solution {

    public int minPathSum(int[][] g) {

        if (g.length == 0) return 0;

        int[][] sum = new int[g.length][g[0].length];

        sum[0][0] = g[0][0];

        for(int i = 1; i < g.length; i++){

            sum[i][0] = g[i][0] + sum[i-1][0];

        }

        for(int i = 1; i < g[0].length; i++){

            sum[0][i] = g[0][i] + sum[0][i-1];

        }        

        for(int i = 1; i < g.length; i ++){

            for(int j = 1; j < g[0].length; j++){

                sum[i][j] = g[i][j] + Math.min(sum[i-1][j], sum[i][j-1]);

            }

        }

        return sum[g.length-1][g[0].length-1];

    }

}

方法二：自底向上 + 一维memo

class Solution {

    public int minPathSum(int[][] g) {

        if (g.length == 0) return 0;

        int[] sum = new int[g[0].length];

        sum[0] = g[0][0];

        for(int i = 1; i < g[0].length; i++){

            sum[i] = g[0][i] + sum[i-1];

        }        

        for(int i = 1; i < g.length; i ++){

            sum[0] = sum[0] + g[i][0];

            for(int j = 1; j < g[0].length; j++){

                sum[j] = g[i][j] + Math.min(sum[j], sum[j-1]);

            }

        }

        return sum[g[0].length-1];

    }

}

Triangle : 矩阵型，求最小值

方法一 ：自定向下

递归 + memo

问题拆分、状态、状态转移方程、初始值，一个都不能少

class Solution {

    Map<Long, Integer> m = new HashMap<>();

    int helper(List<List<Integer>> tri, int row, int col){

        long key = (long)row << 32 | col;

        if(m.containsKey(key)){

            return m.get(key);

        }

        if ( row == 0 && col == 0 ){  //不能忽略此逻辑

            return tri.get(0).get(0);

        }

        int left = Integer.MAX_VALUE;

        int top = Integer.MAX_VALUE;

        if(row > 0){

            if(col < tri.get(row).size() - 1){

                top = helper(tri, row - 1, col);

            }

            if(col > 0){

                left = helper(tri, row - 1, col - 1);

            }

        }

        int val = Math.min(top, left) + tri.get(row).get(col);

        m.put(key, val);

        return val;

    }

    public int minimumTotal(List<List<Integer>> tri) {

        if(tri.size() == 0) return 0;

        int sum = Integer.MAX_VALUE;

        for(int j = 0; j < tri.get(tri.size()-1).size(); j++){

            sum = Math.min(sum, helper(tri, tri.size()-1, j));

        }

        return sum;

    }

}

方法二 ：自底向上

递推 + memo，下面的方法还可以进一步优化

class Solution {

    public int minimumTotal(List<List<Integer>> tri) {

        if(tri.size() == 0) return 0;

        int[] memo = new int[tri.get(tri.size()-1).size()];

        memo[0] = tri.get(0).get(0);

        for(int i = 1; i < tri.size(); i ++){

            for(int j = tri.get(i).size() -1; j >= 0 ; j--){

                if(j == 0){

                    memo[j] = memo[j] + tri.get(i).get(j);

                }

                else if(j == tri.get(i).size() - 1){

                    memo[j] = memo[j-1] + tri.get(i).get(j);

                }

                else{

                    memo[j] = Math.min(memo[j-1], memo[j]) + tri.get(i).get(j);

                }

            }

        }

        int sum = Integer.MAX_VALUE;

        for(int i=0; i<memo.length; i++){

            sum = Math.min(sum, memo[i]);

        }

        return sum;

    }

}

Maximum Square ：矩阵型，求最大最小值

方法一：自底向上

递推 + memo

主要看斜对角线，当前位置能成为多大square，要看左上角位置有多大square。本地弯弯道道挺多。

class Solution {

    public int maximalSquare(char[][] m) {

        if(m.length == 0) return 0;

        int[][] memo = new int[m.length + 1][m[0].length + 1];

        for(int i = 0; i <= m.length; i++ ){

            memo[i][0] = 0;

        }

        for(int i = 0; i <= m[0].length; i++){

            memo[0][i] = 0;

        }

        int maxi = 0;

        for(int i = 0; i < m.length; i++){

            for(int j = 0; j < m[0].length; j++){

                if(m[i][j] != '1'){

                    memo[i+1][j+1] = 0;

                    continue;

                }

                if(memo[i][j] <= 0){

                    memo[i+1][j+1] = 1;

                }

                else {

                    int k = 1;

                    for(; k <= memo[i][j]; k++){

                        if(m[i-k][j] != '1' || m[i][j-k] != '1'){

                            break;

                        }

                    }

                    memo[i+1][j+1] = k;

                }

                //System.out.println("i" + i + " j" + j + " =" + memo[i+1][j+1]);

                maxi = Math.max(memo[i+1][j+1], maxi);

            }

        }

        return maxi * maxi;

    }

}

Range Sum Query 2D - Immutable

方法一 ：自底向上，递推 + memo

class NumMatrix {

    private int[][] memo;

    public NumMatrix(int[][] m) {

        if(m.length == 0 || m[0].length == 0) return;

        memo = new int[m.length][m[0].length + 1];

        for(int i = 0; i < m.length; i++){

            for(int j = 0; j < m[0].length; j++){

                memo[i][j+1] = memo[i][j] + m[i][j];

            }

        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {

        int sum = 0;

        for(int i = row1; i <= row2; i++){

            sum += (memo[i][col2+1] - memo[i][col1]);

        }

        return sum;

    }

}

巴特西

leetcode动态规划笔记二