LeetCode:房屋抢劫犯II C#

Question

https://leetcode.com/problems/house-robber-ii/

你是一个职业抢劫犯，打算抢劫街道上的房屋。每间房子都藏着一定数量的钱。这个地方的所有房屋都被围成一圈。这意味着第一栋房子是最后一栋房子的邻居。同时，相邻的房屋都有安全系统连接，如果两个相邻的房屋在同一晚被闯入，它将自动与警方联系。给出一张代表每所房子的金额的非负整数的清单，确定你今晚可以抢劫的最高金额，而无需报警。例1:输入：2,3,2输出:3解释:你不能抢劫房子1(货币= 2)，然后抢劫房子3(货币= 2)，因为它们是相邻的房屋。示例2:输入：1,2,3,1输出:4解释: Rob 1 (money = 1)，然后rob 3 (money = 3)。你可以抢劫的总数=1+3= 4。

using System;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace CirucularArray
{
    /// <summary>
    /// google interview
    /// https://www.geeksforgeeks.org/maximum-sum-in-circular-array-such-that-no-two-elements-are-adjacent/
    /// https://leetcode.com/problems/house-robber-ii/
    /// </summary>
    [TestClass]
    public class MaximumSumCircularArrayNo2ElementsAreAdjacent
    {
        [TestMethod]
        public void RobberTestEvenArray()
        {
            int[] arr = {1, 2, 3, 4, 5, 1};
            int result = Rob(arr);
            Assert.AreEqual(9, result);

        }
        [TestMethod]
        public void RobberTestOddArray()
        {
            int[] arr = { 5, 1, 2, 10 ,5 };
            int result = Rob(arr);
            Assert.AreEqual(15, result);

        }

        [TestMethod]
        public void TestMethodOneItem()
        {
            int[] arr = {1 };
            int result = Rob(arr);
            Assert.AreEqual(1, result);
        }

        public int Rob(int[] nums)
        {
            if (nums == null || nums.Length == 0)
            {
                return 0;
            }

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

            return Math.Max(Helper(0, nums.Length - 2,nums), Helper(1, nums.Length - 1,nums));
        }

        private int Helper(int start, int end, int[] nums)
        {
            int prevMax = 0;
            int currMax = 0;
            for (int i = start; i <= end; i++)
            {
                int temp = currMax;
                currMax = Math.Max(prevMax + nums[i], currMax);
                prevMax = temp;
            }

            return currMax;
        }
    }
}

Answer 1

以下是解决方案的另一个版本

 public int Rob(int[] nums)
        {
            int n = nums.Length;
            if (n == 0)
            {
                return 0;
            }
            if (n == 1)
            {
                return nums[0];
            }
            int[] dp = new int[n];
            int[] dp2 = new int[n];
            dp[0] = nums[0];
            dp[1] = Math.Max(nums[0], nums[1]);

            dp2[0] = 0; //we "SKIP" nums[0]
            dp2[1] = nums[1];

            for (int i = 2; i < n; i++)
            {
                dp[i] = Math.Max(nums[i] + dp[i - 2], dp[i - 1]);
                dp2[i] = Math.Max(nums[i] + dp2[i - 2], dp2[i - 1]);
            }
            //for dp we can't use n-1 since it is next to nums[0] so we only use n-2
            return Math.Max(dp[n - 2], dp2[n - 1]);

        }