题解 | JAVA #打家劫舍(一)# [P0]

import java.util.*;

// F(i): max profit at nums[i], and rob nums[i]
//   = G(i-1) + nums[i]
// G(i): max profit at nums[i], and do not rob nums[i]
//   = max(F(i-1), G(i-1))
// 空间优化：F/G of i only depends on F/G of i-1
//
// 时间: O(n) 一个for loop
// 空间: O(1) 只存上一轮的F和G
public class Solution {
    public int rob (int[] nums) {
      int f = nums[0], g = 0;
      for (int i = 1; i < nums.length; i++) {
        int f_new = g + nums[i];
        g = Math.max(f, g);
        f = f_new;
      }
      
      return Math.max(f, g);
    }
}