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）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。