多维dp

# 62. 不同路径 (opens new window)

方法一：记忆化搜索

class Solution {
    int m,n;
    int [][] memo;
    public int uniquePaths(int m, int n) {
        this.m = m;
        this.n = n;
        this.memo = new int[m+1][n+1];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(0,0);
    }
    int dfs(int i,int j){
        if(i==m-1 && j==n-1){
            return 1;
        }
        if(i>=m || j>=n){
            return 0;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        return memo[i][j] = dfs(i+1,j)+dfs(i,j+1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：动态规划

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i=0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            dp[0][j] = 1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j] =  dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 64. 最小路径和 (opens new window)

方法一：记忆化搜索

class Solution {
    int m,n;
    int[][] memo;
    int[][] grid;
    public int minPathSum(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.memo = new int[m][n];
        this.grid = grid;
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(0,0);
    }
    int dfs(int i,int j){
        if(i==m-1 && j==n-1){
            return grid[i][j];
        }
        if(i>=m || j>=n){
            return Integer.MAX_VALUE;
        }
        if(memo[i][j]!=-1){
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(i+1,j),dfs(i,j+1))+grid[i][j];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

方法二：动态规划

class Solution {
    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];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 221. 最大正方形 (opens new window)

方法一：记忆化搜索

class Solution {
    char[][] matrix;
    int m;
    int n;
    int[][] memo;
    public int maximalSquare(char[][] matrix) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.memo = new int[m][n];
        this.matrix = matrix;
        int edge = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1')
                    edge = Math.max(edge,dfs(i,j));
            }
        }
        return edge*edge;
    }
    // 以(i,j)的结尾正方形边长
    int dfs(int i,int j){
        if(i>=m || j>=n || matrix[i][j]=='0')
            return 0;
        if(memo[i][j]!=0)
            return memo[i][j];
        return memo[i][j] = 1+Math.min(dfs(i+1,j),Math.min(dfs(i,j+1),dfs(i+1,j+1)));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

← 数位dp DFS→