题解 | #打家劫舍（一）#

C语言写吐了，不想写了。。。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
      //  dp[i] 表示偷至前i家时所窃取的最多金钱
      int size = nums.size();
      std::vector<int> dp(size + 1, 0);
      dp[0] = 0;
      dp[1] = nums[0];
      
      for (int i = 2; i <= size; ++i) {
        dp[i] = std::max(dp[i - 1], dp[i - 2] + nums[i - 1]);
      }
      
      return dp[size];
    }
};

跟跳台阶一样，空间复杂度可以降为1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int rob(vector<int>& nums) {
      int a = 0, b = nums[0], c = nums[0];
      
      for (int i = 2; i <= nums.size(); ++i) {
        c = std::max(b, a + nums[i - 1]);
        a = b;
        b = c;
      }
      
      return c;
    }
};