LeetCode#198 House Robber

問題

有一個職業盜賊想要在某條街上行竊，這條街上有著一整排的房屋，每棟房屋內都有特定數量的金錢，他希望能夠偷到越多錢越好。但是想在這條街行竊有個限制，每兩棟相鄰的房屋之間都有連結保全系統，若他行竊兩棟相鄰的房屋，保全系統就會自動聯繫警察。

給定一個非負整數的list，表示每間房屋內的金錢數量，請問在不驚動保全系統的前提下，竊賊能夠偷到最多的金錢數量是多少？

輸入與輸出

Input: [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.

Input: [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.

方法

使用動態規劃，假設 a_n 為行竊第 n 棟房屋能夠獲得的金錢數量，可得 a_n = max(a_n-2, a_n-3)。

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

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int rob(int* nums, int numsSize) 
{
    if (numsSize == 0)
        return 0;
    
    int i;
    if (numsSize >= 3)
        nums[2] += nums[0];
    for (i = 3; i < numsSize; i++)
        nums[i] += max(nums[i - 2], nums[i - 3]);
    
    if (numsSize == 1)
        return nums[0];
    else if (numsSize == 2)
        return max(nums[0], nums[1]);
    else
        return max(nums[i - 1], nums[i - 2]);
}