package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月17日 15:14
 * @description: 力扣198 打家劫舍
 */
public class Rob {
 public static void main(String[] args) {
 int [] arr = {1,2,3,1};
 System.out.println(new Rob_Solution().rob(arr));
 }
}

class Rob_Solution{
// int max[] = new int[1];
// int [] sum = new int[1];
// public int rob(int[] nums) {
// int t = 0;
// max[0] = -1;
// sum[0] = 0;
// backtrace(nums,max,sum,t);
//
// return max[0];
// }
// public void backtrace(int []nums,int []max,int []sum,int t){
//
// if(t == nums.length-1){
// max[0] = Math.max(sum[0],max[0]);
// System.out.println(sum[0]);
// return;
// }
// for(int i = 0;i<nums.length;i++){
// if((i - t <= 1)){
// continue;
// }
// sum[0] += nums[i];
// backtrace(nums,max,sum,i);
// }
// }

 public int rob(int[] nums){

 if(nums.length == 1){
 return nums[0];
 }
 int []dp = new int[nums.length];

 dp[0] = nums[0];
 dp[1] = Math.max(dp[0],nums[1]);
 if(nums.length ==2){
 return dp[1];
 }
 for(int i = 2;i < nums.length;i++){
 dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);
 }
 return dp[nums.length-1];
 }
}