學(xué)習(xí)動(dòng)態(tài)規(guī)劃|不同路徑、最小路徑和、打家劫舍、打家劫舍iii
62 不同路徑
- 動(dòng)態(tài)規(guī)劃，dp[i][j]表示從左上角到(i,j)的路徑數(shù)量
- dp[i][j] = dp[i-1][j] + dp[i][j-1]
import java.util.Arrays;
public class $62 {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];}public int uniquePaths2(int m, int n) {int[] dp = new int[n];Arrays.fill(dp, 1);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[j] += dp[j-1];}}return dp[n-1];}
}
import java.util.Arrays;
public class $62 {public int uniquePaths2(int m, int n) {int[] dp = new int[n];Arrays.fill(dp, 1);for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {dp[j] += dp[j-1];}}return dp[n-1];}
}
64 最小路徑和
- 動(dòng)態(tài)規(guī)劃，dp[i][j]表示從左上角到(i,j)的最小路徑和
- grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
public class $64 {public int minPathSum(int[][] grid) {for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {if (i==0 && j==0) continue;else if (i!=0 && j==0) grid[i][j] = grid[i-1][j] + grid[i][j];else if (i==0 && j!=0) grid[i][j] = grid[i][j-1] + grid[i][j];else grid[i][j] = Math.min(grid[i-1][j], grid[i][j-1]) + grid[i][j];}}return grid[grid.length-1][grid[0].length-1];}
}
198 打家劫舍
- 動(dòng)態(tài)規(guī)劃，nums[i]表示前i間房屋能偷竊到的最高總金額
- nums[i] = Math.max(nums[i-1], nums[i-2]+nums[i]);
public class $198 {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}if (nums.length == 1) {return nums[0];}nums[1] = Math.max(nums[0], nums[1]);for (int i = 2; i < nums.length; i++) {nums[i] = Math.max(nums[i-1], nums[i-2]+nums[i]);}return nums[nums.length-1];}
}
337 打家劫舍iii
- 樹(shù)形動(dòng)態(tài)規(guī)劃
- 我們可以用 f(o)表示選擇 o節(jié)點(diǎn)的情況下，o節(jié)點(diǎn)的子樹(shù)上被選擇的節(jié)點(diǎn)的最大權(quán)值和；
- g(o)表示不選擇 o節(jié)點(diǎn)的情況下，o節(jié)點(diǎn)的子樹(shù)上被選擇的節(jié)點(diǎn)的最大權(quán)值和；
- l 和 r代表 o 的左右孩子。
- 當(dāng) o 被選中時(shí)：o 的左右孩子都不能被選中，
-
故 o 被選中情況下子樹(shù)上被選中點(diǎn)的最大權(quán)值和為 l和 r不被選中的最大權(quán)值和 + o的值
-
f(o)=g(l)+g(r)+o.val
- 當(dāng) o不被選中時(shí)，o的左右孩子可以被選中，也可以不被選中。
-
對(duì)于 o的某個(gè)具體的孩子 x，它對(duì) o 的貢獻(xiàn)是 x被選中和不被選中情況下權(quán)值和的較大值。
-
g(o)=max{f(l),g(l)} + max{f(r),g(r)}
import java.util.HashMap;
import java.util.Map;
public class $337 {Map<TreeNode, Integer> f = new HashMap<>();Map<TreeNode, Integer> g = new HashMap<>();public int rob(TreeNode root) {process(root);return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));}private void process(TreeNode root) {if (root == null) {return;}process(root.left);process(root.right);f.put(root, root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));g.put(root, Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0))+ Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));}public int rob2(TreeNode root) {int[] rootStatus = process2(root);return Math.max(rootStatus[0], rootStatus[1]);}private int[] process2(TreeNode root) {if (root == null) {return new int[]{0, 0};}int[] l = process2(root.left);int[] r = process2(root.right);int selected = root.val + l[1] + r[1];int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);return new int[]{selected, notSelected};}
}
