题解 | JAVA #打家劫舍(二)# [P2]

跟(一)同样的解法，dp定义也完全不用变。跑两遍而已

环形只影响最后一个房子的选择:
 - 如果偷了第0个房子，那最后一个房子就偷不了。
 - 如果不偷第0个房子，那最后一个房子可以选择偷或着不偷
那岂不是把两个情况都跑一遍 挑个更好的就行了。。。

偷了第0个房子：
在第1个房子时，
   g(1)=nums[0] ～ 不偷1
   f(1)=nums[0] ～ 偷1，理论上1不能偷，但是你就想象你也进了1，但是空手而归
因为偷了0，所以在最后一个房子n只能选g(n)

不偷第0个房子：
在第1个房子，
   g(1)=0 ～ 不偷1
   f(1)=nums[1] ～ 偷1
因为没偷0，所以在最后一个房子n选max(g(n), f(n))

时间: O(n) for-loop 跑两遍
空间: 还是 O(1)

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))
public class Solution {
    public int rob (int[] nums) {
      if (nums.length == 1) return nums[0];
      
      // rob 0th house
      int f = nums[0], g = nums[0]; // profit at nums[1]
      for (int i = 2; i < nums.length; i++) {
        int f_new = g + nums[i];
        g = Math.max(f, g);
        f = f_new;
      }
      int profitRob1 = g;  // can't rob last house
      
      // don't rob 0th house
      f = nums[1]; g = 0;  // profit at nums[1]
      for (int i = 2; i < nums.length; i++) {
        int f_new = g + nums[i];
        g = Math.max(f, g);
        f = f_new;
      }
      int profitNotRob1 = Math.max(f, g);
      
      return Math.max(profitRob1, profitNotRob1);
    }
}