Header Ad

Leetcode House Robber problem solution

In this Leetcode House Robber problem solution, You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Leetcode House Robber problem solution


Problem solution in Python.

class Solution:
    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)
        if n < 2:
            return nums[0]

        dp = {}
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        return dp[n-1]



Problem solution in Java.

class Solution {
	public int rob(int[] nums) {
		if(nums.length == 0) return 0;
		if(nums.length == 1) return nums[0];
		if(nums.length == 2) return Math.max(nums[0], nums[1]);

		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		dp[1] = Math.max(nums[0], nums[1]);

		for(int i = 2; i < nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
		}

		return dp[nums.length - 1];
	}
}


Problem solution in C++.

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0], nums[1]);
        vector<int> cost(nums.size(),0);
        cost[0]=nums[0];
        cost[1]=max(nums[0], nums[1]);
        for(int i=2;i<nums.size();i++)
            cost[i]=max(cost[i-1], (cost[i-2]+nums[i]));
        return cost[nums.size()-1];
    }
};


Problem solution in C.

int max(int a, int b){
    if (a >= b)
        return a;
    return b;
}

int rob(int* nums, int numsSize){
    if(numsSize < 1) 
        return 0;
    int cur = nums[0], p2p = 0, prev = nums[0];
    for(int i = 1; i<numsSize ; i++){
        cur = max(p2p+nums[i], prev);
        p2p = prev;
        prev = cur;
    }
    return cur;
    
}


Post a Comment

0 Comments