LeetCode #198: House Robber

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Solution

题意

在一条街上有n户人家（假设街道是一条很长的直线，所有的房子按照直线排列），每户人家家里有一定数量的财产，以数组nums给出，nums[i]表示第i户人家的财产数目。
相邻的两户人家连接了报警装置，如果相邻的两户人家在同一晚被盗窃，那么就会触发报警系统。
现在假设你是一个盗贼，偷盗的目标就是这条街上的人家，如何在不触发报警装置的情况下，使偷到的财产数额达到最大？输出这个最大值。

分析

这是一个动态规划的问题，按照动态规划的思想来看，求解此问题的关键依然是将问题划分成规模更小的子问题，然后找出递推关系，下面是我的思考过程（但是走了一些弯路，我这里选择完全地重现我的思路，给以后求解动规问题留下一些经验/教训之类的）：
因为这是一个线性序列，对于每一户来说，选择不抢可记为0，选择抢可记为1，最后得到的其实是一个0-1序列。那么将要求的解转化成0-1序列的形式有没有用呢？有一些用处，可以用来记录解的具体情况，但此问中只要求得最大值即可，不关注具体的解。但是在逻辑上来说，我们将自然语言转化成了计算机语言。
接下来考虑怎么划分子序列，以及如何找出递推关系。因为是单个线性序列，那么选择其实就只有两种，一种是从长度为i的序列出发(i = 1, 2, ..., n)，对于第i+1户，前面长度为i的0-1序列假定已经是最优解了，那么i+1选择0（不抢）或1（抢）只依赖于第i户的值：如果第i户是0，那么i+1可以选择0或1,；如果第i户是1，那么i+1只能选择0。
那么到底如何选择呢，这时我们两种情况都要考虑，具体的递推关系式是：best[i] = max(best[i-1], best[i - 2] + nums[i-1])。
来看这个式子：数组best[i]保存的信息是，到第i-1户为止（第i-1户也是被决策过的）的最优解（即整个序列的子序列[0...i]的最优解——可抢财产和的最大值）；而递推关系说明的是，要决定第[i-1]户抢还是不抢，取决于两个值中哪个最大——max(不抢第i-1户的情况下抢劫财产总额，抢了第i-1户的情况下抢劫财产总额）

Code - Version1（空间复杂度为O(n)）

//Runtime: 3ms
class Solution {
public:
    int max(const int & a, const int & b){
        return a > b ? a : b;
    }
    int rob(vector<int>& nums) {
        if (nums.empty())   return 0;
        
        vector<int> best;
        int numSize = nums.size();
        best.resize(numSize + 1);
        best[0] = 0;
        best[1] = nums[0];
        for (int i = 2; i < numSize + 1; i++){
            best[i] = max(best[i - 1], best[i - 2] + nums[i - 1]);
        }
        return best[numSize];
    }
};

Code - Version2（空间复杂度为O(1)）

//Runtime: 3ms
class Solution {
public:
    int max(const int &a, const int &b){
        return (a > b ? a : b);
    }
    int rob(vector<int>& nums) {
        if (nums.empty())   return 0;
        int size = nums.size();
        int rob_false = 0;
        int rob_true = 0;
        for (int i = 0; i < size; i++){
            int tmp = rob_false;
            rob_false = max(rob_false, rob_true);
            rob_true = max(tmp + nums[i], rob_true);
        }

        return max(rob_false, rob_true);
    }
};