213.Rob.cs

// 213. House Robber II
// You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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.
// Example 1:
// Input: nums = [2,3,2]
// Output: 3
// Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
// Example 2:
// Input: nums = [1,2,3,1]
// Output: 4
// Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
// Total amount you can rob = 1 + 3 = 4.
// Example 3:
// Input: nums = [1,2,3]
// Output: 3
// Constraints:
// 1 <= nums.length <= 100
// 0 <= nums[i] <= 1000


//Approch: same as 198, but here first and last cant be include at once.
public class Solution {
    public int Rob(int[] nums) {
        int[] dp = new int[nums.Length];
        if(nums.Length == 1)
            return nums[0];
        if(nums.Length == 2)
            return Math.Max(nums[1],nums[0]);
        if(nums.Length == 3)
            return Math.Max(nums[1],Math.Max(nums[0],nums[2]));

        //Assume array without last element
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0]+nums[2];
        for(int i = 3; i<nums.Length-1;i++){
            dp[i] = nums[i] + Math.Max(dp[i-2],dp[i-3]);
        }
        int profi1 = Math.Max(dp[nums.Length-2],dp[nums.Length-3]);
        Array.Fill(dp,0);

        //Assume array without first element
        dp[0] = 0;
        dp[1] = nums[1];
        dp[2] = nums[2];
        for(int i = 3; i<nums.Length;i++){
            dp[i] = nums[i] + Math.Max(dp[i-2],dp[i-3]);
        }
        int profi2 = Math.Max(dp[nums.Length-1],dp[nums.Length-2]);

        return Math.Max(profi1,profi2);
    }
}