LeetCode 213. House Robber II

House Robber II

The trick is to find the max value between robbing 0 to n-2 and 1 to n-1, so that we avoid the rounding issue.

public class Solution {
    public int Rob(int[] nums) {
        int len = nums.Length;
        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[] h = new int[nums.Length];
        h[0] = nums[0];
        h[1] = nums[1];
        for(int i = 2; i < nums.Length-1; i++){
            int max = int.MinValue;
            for(int j = 0; j < i - 1; j++){
                max = Math.Max(nums[i] + h[j], max);
            }
            h[i] = max;
        }
        int h1 = Math.Max(h[len-2], h[len-3]);
        
        h[1] = nums[1];
        h[2] = nums[2];
        for(int i = 3; i < nums.Length; i++){
            int max = int.MinValue;
            for(int j = 1; j < i - 1; j++){
                max = Math.Max(nums[i] + h[j], max);
            }
            h[i] = max;
        }
        int h2 = Math.Max(h[len-1], h[len-2]);
        
        return Math.Max(h1, h2);
    }
}
Tagged

Leave a Reply

Your email address will not be published. Required fields are marked *