package dynamic;

/**题目:抢劫连排房子
 * y: a[]{8,1,2,9,6}
 * 要求计算最大值,唯一的限制条件就是数组间计算的数字不能相邻
 * 本地计算结果为:8+9=17
 * @Author Gavin
 * @date 2022年01月09日 10:36
 */
public class solution_4 {
 /**
 * 解题思路:本题是一个动态规划题目
 * [8,1,2,9,6]
 * 本题目的状态和状态转移的方程为:
 * house money
 * 一个房子和能抢劫的最大money为: 8 8
 * 二个房子和能抢劫的最大money为: 8,1 8
 * 三个房子和能抢劫的最大money为: 8,1,2 max(8,8+2)=10
 * 四个房子和能抢劫的最大money为: 8,1,2,9 max(10,8+9)=17
 * ...
 *
 * 可以得出规律:
 * {
 * d(i)=max(d(i-1),d(i-2)+nums[i])
 * d(0)=num(10)
 * d(1)=max(num[0],nums[1])
 *
 * }
 *
 */
 //Time:O(n) Space:O(n)
 public static int solution(int[] nums){
 if(nums==null||nums.length==0)return 0;
 if(nums.length==1)return nums[0];
 //定义一个状态数组
 int[] d=new int[nums.length];
 d[0]=nums[0];
 d[1]=Math.max(nums[0],nums[1]);
 //i从2开始
 for (int i = 2; i < nums.length; i++) {
 d[i]=Math.max(d[i-1],d[i-2]+nums[i]);
 }
 return d[nums.length-1];
 }

 /**
 * 该方法是上面的优化版本,主要是优化空间复杂度,
 * 因为我们只需要关注前1个和前两个的值就行,所以只需要两个
 * 变量来存储就行了。
 */
 //Time:O(n) Space:O(1)
 public int solution_2(int[] nums){
 if(nums==null||nums.length==0)return 0;
 int prev1=0,prev2=0;
 for (int num:nums){
 int cur=Math.max(prev1,prev2+num);
 prev2=prev1;
 prev1=cur;
 }
 return prev1;
 }

 public static void main(String[] args) {
 int[] arr=new int[]{8,1,2,8,9};
 System.out.println(solution(arr));
 }
}