打家劫舍问题
不能偷相邻的两家
- dp定义：在到第
i家所获得的最大收益是dp[i]
- 状态转移方程：取下面两者的最大值，
dp[i][j] = Math.max(dp[i-2] + nums[i], dp[i-1])
- 如果我选择当前第
i家的话， 那就不能偷前一家也就是只能是，dp[i-2] + nums[i]
- 如果我不偷当前一家的话，那就本次没有收益，和在在第
i-1家的收益相同， dp[i-1]
- 初始化： 只有一家那就偷这一家，
dp[0] = nums[0], 如果有两家，就选最大的一家偷，dp[1] = Math.max(nums[0], nums[1])
- 本质上还是看从哪一家先偷比较好
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n <= 1) return nums[0];
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++){
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n-1];
}
}
|
这是一个打家劫舍的升级问题，因为涉及到环的问题，其实就是首尾是不能同时被选择的
- 那么我们就可以把这个问题，简化为两个数组，a. 0
len-2 b. 1len-1，这样首尾就不可能被同时选择。
- 相当于做两边上一个
打家劫舍问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
int res1 = rober(Arrays.copyOfRange(nums, 0, nums.length - 1));
int res2 = rober(Arrays.copyOfRange(nums, 1, nums.length));
return Math.max(res1, res2);
}
public int rober(int[] nums){
int n = nums.length;
if (n <= 1) return nums[0];
int[] dp= new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++){
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n-1];
}
}
|
这是一个树的问题，引入一个叫树形dp的概念，其实就是相当于对这个树进行遍历的问题
- 这里dp数组，在树的每一层都有一个，包含了两个元素，选当前节点的最大值，和不选当前节点的最大值。
- 采用后序遍历可以很好的对左右子树的贡献进行计算。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int rob(TreeNode root) {
int[] res = rober(root);
return Math.max(res[0], res[1]);
}
public int[] rober(TreeNode root){
if (root == null){
return new int[]{0, 0};
}
int[] left = rober(root.left);
int[] right = rober(root.right);
int xuan = left[0] + right[0] + root.val;
int buxuan = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{buxuan, xuan};
}
}
|
