Leetcode:198

Posted on | Comments: | Views:
DP

198. House Robber

题目理解:

给出一个数组, 不能取相邻的数, 求能取的最大值

思路:

用 f[i] 记录状态, 表示后 i 个数中能取的最大值; 问题的答案是 f[n-1]


对于 f[i] , 考虑要不要取 num[n-1-i], 分为两种情况, 如果取, 那么就不能取 num[n-1-i+1], 那么 f[i] = num[n-1-i] + f[i-2]; 若不取, 那么就是从 n-1-i+1 开始到最后取最大值, 也就是 f[i-1], 那么 f[i] = f[i-1]; 这样就能够写出状态转移方程 f[i] = max{ num[n-1-i] + f[i-2], f[i-1] }


边界状态, f[0] = 1, f[1] = max{num[n-1], num[n-2]}, 这里自己思考一下就能明白;

小结:

简单的动态规划题

Submission Detail:

code:

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
class Solution {
public:
    vector<int> num;
    vector<int> f;
    int n;
    int rob(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        num = nums;
        n = num.size();
        f.resize(n, 0);
        f[0] = num[n-1];
        f[1] = max(num[n-1], num[n-2]);
        find(n-1);

        return f[n-1];
    }

    void find(int x) {
        if (x < 2 || f[x] != 0) {
            return;
        }
        find(x-1);
        find(x-2);
        f[x] = max(num[n-1-x] + f[x-2], f[x-1]);
    }
};