algo-aha

抢劫房子

• https://leetcode.com/problems/house-robber

设dp[i]表示抢了nums[0..i]后的最大值，根据抢没抢nums[i]，dp[i] = max( dp[i-1], nums[i]+dp[i-2] )，初始dp[-2]=dp[-1]=0

• https://leetcode.com/problems/house-robber-ii

int rob(vector<int>& nums) {
    if (nums.empty()) return 0;
    const int N = nums.size();
    if (N == 1) return nums[0];
    // 相邻房子不能同时抢，从某对相邻房子中间切开，就能得两个无循环的子问题。
    // 比如从首尾这对相邻房子处切开：rob(nums,1,n-1)和rob(nums,0,n-2)
    return max(robSub(nums, 1, N - 1), robSub(nums, 0, N - 2));
}
// rob nums[from,to]
int robSub(const vector<int> &nums, int from, int to) {
    // 设dp[i]表示抢了nums[from..i]后的最大值，from<=i<=to
    // dp[i] = max( dp[i-1], nums[i]+dp[i-2] )，初始dp[-2]=dp[-1]=0
    // 递推式只依赖于前两项，记前两项为prev2和prev1
    int prev2 = 0, prev1 = 0;
    for (int i = from; i <= to; i++) {
        int curr = max(prev1, nums[i] + prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

• https://leetcode.com/problems/house-robber-iii

int rob(TreeNode* root) {
    // 问题只有两种状态：抢没抢root，子问题也需返回这两种状态
    auto ans = robSub(root);
    return max(ans[0], ans[1]);
}

// 设子问题返回没抢ans[0]和抢ans[1]两种情况下各自的最大值
vector<int> robSub(TreeNode *root) {
    if (!root) return { 0, 0 };
    auto left = robSub(root->left);
    auto right = robSub(root->right);
    int noRobRoot = max(left[0], left[1]) + max(right[0], right[1]);
    int robRoot = root->val + left[0] + right[0];
    return { noRobRoot, robRoot };
}

• https://leetcode.com/problems/delete-and-earn

删除相邻数字的最大得分，相邻数字类似于相邻房子，变成房子抢劫问题

int deleteAndEarn(vector<int>& nums) {
	// 取数num后删除num-1和num+1，
	// 类似房子抢劫问题，连续值类似于相邻房子
	unordered_map<int, int> count;
	for (int num : nums) {
		count[num]++;
	}

	const int N = 1e5;  // nums[i]在范围[1..1e5]
	// 设dp[i]表示值范围[1..i]的最大得分，1<=i<=N
	// dp[i] = max(dp[i-2] + i*count[i] /*取i*/, dp[i-1] /*不取i*/)
	// dp[i]只依赖前两项，记前两项为prev2、prev1
	int prev2 = 0, prev1 = 0;
	for (int i = 1; i <= N; i++) {
		int curr = max(prev2 + i * count[i], prev1);
		prev2 = prev1;
		prev1 = curr;
	}
	return prev1;
}