3840. House Robber V

中文文档

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed and is protected by a security system with a color code.

You are given two integer arrays nums and colors, both of length n, where nums[i] is the amount of money in the ith house and colors[i] is the color code of that house.

You cannot rob two adjacent houses if they share the same color code.

Return the maximum amount of money you can rob.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

• 1 <= n == nums.length == colors.length <= 105
• 1 <= nums[i], colors[i] <= 105

Solutions

Solution 1: Dynamic Programming

We define two variables $f$ and $g$, where $f$ represents the maximum amount when the current house is not robbed, and $g$ represents the maximum amount when the current house is robbed. Initially, $f = 0$ and $g = nums[0]$. The answer is $\max(f, g)$.

Next, we traverse starting from the second house:

• If the current house has the same color as the previous house, then $f$ is updated to $\max(f, g)$, and $g$ is updated to $f + nums[i]$.
• If the current house has a different color from the previous house, then $f$ is updated to $\max(f, g)$, and $g$ is updated to $\max(f, g) + nums[i]$.

Finally, return $\max(f, g)$.

The time complexity is $O(n)$, where $n$ is the number of houses. The space complexity is $O(1)$.

Python3

class Solution:
    def rob(self, nums: List[int], colors: List[int]) -> int:
        n = len(nums)
        f, g = 0, nums[0]
        for i in range(1, n):
            if colors[i - 1] == colors[i]:
                f, g = max(f, g), f + nums[i]
            else:
                f, g = max(f, g), max(f, g) + nums[i]
        return max(f, g)

Java

class Solution {
    public long rob(int[] nums, int[] colors) {
        int n = nums.length;
        long f = 0, g = nums[0];
        for (int i = 1; i < n; i++) {
            if (colors[i - 1] == colors[i]) {
                long gg = f + nums[i];
                f = Math.max(f, g);
                g = gg;
            } else {
                long gg = Math.max(f, g) + nums[i];
                f = Math.max(f, g);
                g = gg;
            }
        }
        return Math.max(f, g);
    }
}

C++

class Solution {
public:
    long long rob(vector<int>& nums, vector<int>& colors) {
        int n = nums.size();
        long long f = 0, g = nums[0];
        for (int i = 1; i < n; i++) {
            if (colors[i - 1] == colors[i]) {
                long long gg = f + nums[i];
                f = max(f, g);
                g = gg;
            } else {
                long long gg = max(f, g) + nums[i];
                f = max(f, g);
                g = gg;
            }
        }
        return max(f, g);
    }
};

Go

func rob(nums []int, colors []int) int64 {
	n := len(nums)
	var f int64 = 0
	var g int64 = int64(nums[0])

	for i := 1; i < n; i++ {
		if colors[i-1] == colors[i] {
			f, g = max(f, g), f+int64(nums[i])
		} else {
			f, g = max(f, g), max(f, g)+int64(nums[i])
		}
	}

	return max(f, g)
}

TypeScript

function rob(nums: number[], colors: number[]): number {
    const n = nums.length;
    let f = 0;
    let g = nums[0];

    for (let i = 1; i < n; i++) {
        if (colors[i - 1] === colors[i]) {
            [f, g] = [Math.max(f, g), f + nums[i]];
        } else {
            [f, g] = [Math.max(f, g), Math.max(f, g) + nums[i]];
        }
    }

    return Math.max(f, g);
}

Rust

impl Solution {
    pub fn rob(nums: Vec<i32>, colors: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut f: i64 = 0;
        let mut g: i64 = nums[0] as i64;

        for i in 1..n {
            if colors[i - 1] == colors[i] {
                let gg = f + nums[i] as i64;
                f = f.max(g);
                g = gg;
            } else {
                let gg = f.max(g) + nums[i] as i64;
                f = f.max(g);
                g = gg;
            }
        }

        f.max(g)
    }
}