[数据结构与算法]Leetcode198. 打家劫舍（CPP）

题目分析

最值型题目，考虑使用动态规划

编程

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        // 序列型动态规划
        vector<long> f(n + 1);
        f[1] = nums[0];
        for (int i = 2; i <= n; ++i) {
            f[i] = max(f[i - 1], f[i - 2] + nums[i - 1]);
        }

        return f[n];
    }
};

运行结果