leetCode 213. House Robber II | Medium | Dynamic Programming

213. House Robber II

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

題目大意：

此題是 198. House Robber 的更新版。之前已經做過。連結如下：

<a href="http://qiaopeng688.blog.51cto.com/3572484/1844956" target="_blank">http://qiaopeng688.blog.51cto.com/3572484/1844956</a>

第一版的房間形成的街道是一條直線。

第二版的房間形成的街道是成一個圓。

思路：

因為圓的首尾是相鄰的，是以選首不能選尾，選尾不能選首。是以有了下面的思路。

求出不選尾的最大值。也就是數組中a[0]到a[N-1]求出最大值。

求出不選首的最大值。也就是數組中a[1]到a[N]求出最大值。

比較1，2的最大值，然後得到最終結果。

代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

<code>class</code> <code>Solution {</code>

<code>public</code><code>:</code>

<code>    </code><code>int</code> <code>rob(vector&lt;</code><code>int</code><code>&gt;&amp; nums) </code>

<code>    </code><code>{</code>

<code>        </code><code>int</code> <code>numLength = nums.size();</code>

<code>        </code><code>if</code> <code>(nums.empty())</code>

<code>            </code><code>return</code> <code>0;</code>

<code>        </code><code>if</code> <code>(1 == numLength)</code>

<code>            </code><code>return</code> <code>nums[0];</code>

<code>        </code><code>if</code> <code>(2 == numLength)</code>

<code>            </code><code>return</code> <code>nums[0] &gt; nums[1] ? nums[0] : nums[1];</code>

<code>        </code><code>int</code> <code>*maxV1 = </code><code>new</code> <code>int</code><code>[nums.size() - 1];</code><code>// 0---nums.size()-2</code>

<code>        </code><code>int</code> <code>*maxV2 = </code><code>new</code> <code>int</code><code>[nums.size() - 1];</code><code>// 1---nums.size()-1</code>

<code>        </code><code>int</code> <code>result = 0;</code>

<code>        </code><code>maxV1[0] = nums[0];</code>

<code>        </code><code>maxV1[1] = nums[0] &gt; nums[1] ? nums[0] : nums[1];</code>

<code>    </code> 

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 2; i &lt; nums.size() - 1; ++i)</code>

<code>        </code><code>{</code>

<code>            </code><code>maxV1[i] = max(maxV1[i - 2] + nums[i], maxV1[i - 1]);</code>

<code>        </code><code>}</code>

<code>        </code><code>maxV2[0] = nums[1];</code>

<code>        </code><code>maxV2[1] = nums[1] &gt; nums[2] ? nums[1] : nums[2];</code>

<code>        </code><code>for</code> <code>(</code><code>int</code> <code>i = 3; i &lt; nums.size(); ++i)</code>

<code>            </code><code>maxV2[i - 1] = max(maxV2[i - 3] + nums[i], maxV2[i - 2]);</code>

<code>        </code><code>result = max(maxV1[nums.size() - 2], maxV2[nums.size() - 2]);</code>

<code>        </code><code>delete</code> <code>maxV1;</code>

<code>        </code><code>delete</code> <code>maxV2;</code>

<code>        </code><code>maxV1 = NULL;</code>

<code>        </code><code>maxV2 = NULL;</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>};</code>

總結：

代碼瞬息萬變，解決萬千問題。哈哈哈哈。有意思。

本文轉自313119992 51CTO部落格，原文連結:http://blog.51cto.com/qiaopeng688/1844994