198
不能相邻两间屋
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int first = nums[0], second = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
213
房子是一圈
class Solution {
public int rob(int[] nums) {
int length = nums.length;
if (length == 1) {
return nums[0];
} else if (length == 2) {
return Math.max(nums[0], nums[1]);
}
return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
}
public int robRange(int[] nums, int start, int end) {
int first = nums[start], second = Math.max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
int temp = second;
second = Math.max(first + nums[i], second);
first = temp;
}
return second;
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/house-robber-ii/solution/da-jia-jie-she-ii-by-leetcode-solution-bwja/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
337
房子成树状
树形DP分析清楚某一个节点和它儿子之间的关系（分析清楚某一个家庭的关系），递归做就可以了
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int rob(TreeNode* root) {
auto f = dfs(root);
return max(f[0], f[1]);
}
vector<int> dfs(TreeNode* u) {
if (!u) return {
0, 0};
auto x = dfs(u->left), y = dfs(u->right);
return {
max(x[0], x[1]) + max(y[0], y[1]), x[0] + y[0] + u->val};
}
};
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/481425/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2560
看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。
class Solution {
//用DP判断当前二分查找值是否有效
public int minCapability(int[] nums, int k) {
int left = 0, right = (int) 1e9;
while (left <= right) {
int mid = (left + right) >>> 1;
int f0 = 0, f1 = 0;
for (int x : nums)
if (x > mid) f0 = f1;
else {
int tmp = f1;
f1 = Math.max(f1, f0 + 1);
f0 = tmp;
}
if (f1 >= k) right = mid - 1;
else left = mid + 1;
}
return left;
}
}
// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/house-robber-iv/solutions/2093952/er-fen-da-an-dp-by-endlesscheng-m558/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
