62.不同路径

✒解题思路：

  1. DP 
    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
    29
    30
    31
    32
    33
    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 i = 0; i < n; i++) {
    			dp[0][i] = 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];
    	}
    }
    //优化之后
    class Solution {
    	public int uniquePaths(int m, int n) {
    		int[] dp = new int[n];
    		for (int i = 0; i < n; i++) {
    			dp[i] = 1;
    		}
    		for (int i = 1; i < m; i++) {
    			dp[0] = 1;
    			for (int j = 1; j < n; j++) {
    				dp[j] = dp[j] + dp[j - 1];
    			}
    		}
    		return dp[n - 1];
    	}
    }

64.最小路径和

✒解题思路：

  1. DP
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 minPathSum(int[][] grid) {
		int m = grid.length;
		int n = grid[0].length;
		if (m <= 0 || n <= 0) {
			return 0;
		}
		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 i = 1; i < n; i++) {
			dp[0][i] = dp[0][i - 1] + grid[0][i];
		}
		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];
	}
}

72.编辑距离

✒解题思路：

  1. DP
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 minDistance(String word1, String word2) {
		int m = word1.length();
		int n = word2.length();

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

		for (int i = 1; i <= m; i++) {
			dp[i][0] = dp[i - 1][0] + 1;
		}
		for (int i = 1; i <= n; i++) {
			dp[0][i] = dp[0][i - 1] + 1;
		}
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1];
				} else {
					dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
				}
			}
		}
		return dp[m][n];
	}
}

695.岛屿的最大面积

✒解题思路：

  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
class Solution {
	public int maxAreaOfIsland(int[][] grid) {
		int result = 0;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				result = Math.max(result, dfs(i, j, grid));
			}
		}
		return result;
	}

	private int dfs(int i, int j, int[][] grid) {
		if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == 0) {
			return 0;
		}
		int num = 1;
		grid[i][j] = 0;
		num += dfs(i - 1, j, grid);
		num += dfs(i + 1, j, grid);
		num += dfs(i, j - 1, grid);
		num += dfs(i, j + 1, grid);
		return num;
	}
}