dp第16天

64. 最小路径和

评论区建议把这题难度改成简单题。。。笑死我了。。

/**
 64. 最小路径和
 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

 说明：每次只能向下或者向右移动一步。



 示例 1：


 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 输出：7
 解释：因为路径 1→3→1→1→1 的总和最小。
 示例 2：

 输入：grid = [[1,2,3],[4,5,6]]
 输出：12


 提示：

 m == grid.length
 n == grid[i].length
 1 <= m, n <= 200
 0 <= grid[i][j] <= 100

 * @author zeroheart
 *
 */


public class Question64 {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

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

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

        for(int j = 1; j<n; j++){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

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

    public static void main(String[] args) {
    }
}

221. 最大正方形

这题有直接看答案了。。注意dp的定义

dp[i][j]表示右下角是[i][j]的正方形的最大边长。这个边长dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

/**
 221. 最大正方形
 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。



 示例 1：


 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 输出：4
 示例 2：


 输入：matrix = [["0","1"],["1","0"]]
 输出：1
 示例 3：

 输入：matrix = [["0"]]
 输出：0


 提示：

 m == matrix.length
 n == matrix[i].length
 1 <= m, n <= 300
 matrix[i][j] 为 '0' 或 '1'

 * @author zeroheart
 *
 */


public class Question221 {
    public int maximalSquare(char[][] matrix) {
        // 这题有直接看答案了。。

        // dp[i][j]表示右下角是[i][j]的正方形的最大边长。这个边长dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1

        int max = 0;
        if(matrix==null || matrix.length == 0 || matrix[0].length == 0) return max;

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

        int[][] dp = new int[m][n];
        for(int i = 0; i<m; i++){
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
                max = 1;
            }
        }

        for(int j = 0; j<n; j++){
            if(matrix[0][j] == '1'){
                dp[0][j] = 1;
                max = 1;
            }
        }

        for(int i = 1; i<m; i++){
            for(int j = 1; j<n; j++){
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(Math.min(dp[i][j-1], dp[i-1][j]),dp[i-1][j-1]) + 1;
                }
                max = Math.max(max, dp[i][j]);
            }
        }

        return max * max;
    }

    public static void main(String[] args) {
    }
}