leetcode-198.打家劫舍

1. 题目

2. 解答

dp[i]表示第i个位置的偷窃最大金额；
room[i]表示第i间房间的现金；
dp[0] = room[0];
dp[1] = max(room[0], room[1]);
dp[i] = max(dp[i-1], dp[i-2] + room[i]);

#include 

int max(int a, int b)
{
    return a > b? a:b;
}

int solve(int num[], int len)
{
    int dp[len];
    if (len == 0) return 0;

    if (len == 1) return num[0];
    if (len == 2) return max(num[0], num[1]);

    dp[0] = num[0];
    dp[1] = max(num[0], num[1]);

    for (int i = 2; i < len; i++) {
        dp[i] = max(dp[i -1], dp[i -2] + num[i]);
    }

    return dp[len -1];

}

int main()
{
    int len;
    scanf("%d", &len);

    int num[len];

    for (int i = 0; i < len; i++) {
        scanf("%d", &num[i]);
    }

    int result = solve(num, len);

    printf("result:%d\n", result);

    return 0;
}
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
39
40
41
42
43

运行：

G3-3579:~/data/source/leetcode$ gcc 198.c
G3-3579:~/data/source/leetcode$ ./a.out 
4
1 2 3 1
result:4
G3-3579:~/data/source/leetcode$ ./a.out 
5
2 7 9  3 1
result:12
1
2
3
4
5
6
7
8
9