Brooke

一、題目

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.

 

Example 1:

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 2:

Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.

 

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

 

二、程式作法

 /*Dynamic Programming - use store array*/
public class Solution
{
    public int[] res = Array.Empty<int>();
    public int[] nums = Array.Empty<int>();
    public int Rob(int[] nums)
    {
        res = new int[nums.Length];

        if (nums.Length == 1)
            return nums[0];

        res[0] = nums[0];
        if (nums.Length == 2)
            return Math.Max(res[0], nums[1]);

        res[1] = Math.Max(res[0], nums[1]);

        this.nums = nums;
        Helper(2);
        return res[nums.Length - 1];
    }

    public void Helper(int idx)
    {
        while (idx < nums.Length)
        {
            res[idx] = Math.Max(nums[idx] + res[idx - 2], res[idx - 1]);
            idx++;
        }
    }
}

/*Dynamic Programming - none use store array*/
/*
public class Solution
{
    public int[] res = Array.Empty<int>();
    public int Rob(int[] nums)
    {
        return helper(nums, nums.Length - 1);
    }

    public int helper(int[] nums, int ind)
    {
        if (ind == 0)
            return nums[0];
        else if (ind == 1)
            return Math.Max(nums[0], nums[1]);
        else
            return Math.Max(helper(nums, ind - 1), nums[ind] + helper(nums, ind - 2));
    }
}
*/

/*Depth-first Search (Time Limit Exceeded)*/
/*
public class Solution
{
    public int Rob(int[] nums)
    {
        if (nums.Length == 1)
            return nums[0];

        return Math.Max(helper(nums, 0), helper(nums, 1));
    }

    public int helper(int[] nums, int ind)
    {
        if (ind + 2 >= nums.Length && ind + 3 >= nums.Length)
            return nums[ind];

        if (ind + 3 >= nums.Length)
            return nums[ind] + helper(nums, ind + 2);
        else
            return nums[ind] + Math.Max(helper(nums, ind + 2), helper(nums, ind + 3));
    }
}
*/

 

三、思路筆記

題目要的是從一陣列取出不連續元素間隔中，所有加總元素之最大值。

Dynamic Programming

我們來個別記錄不同長度的陣列子集之結果，來求得最後解。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Depth-First Search