package leecode;

/**
 * 198. 打家劫舍
 *
 *
 *你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，
 * 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 *如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * @author Tang
 * @date 2021/9/16
 */
public class Rob {


    /**
     * 我是一个bu会动态规划的小偷
     * n :房间号n
     * f(n) :按顺序 到n号房的可偷最大金额
     * f(n) = Max(f(n-2) + V(n), f(n-1))
     * base :f(1) = nums[1] ;  f(2) = Max(nums[1], nums[2])
     *
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }

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

        //构建dp tables
        int[] tables = new int[nums.length];
        for(int i = 0; i < nums.length; i++) {
            if(i == 0){
                tables[i] = nums[i];
                continue;
            }
            if(i == 1) {
                tables[i] = Math.max(nums[0], nums[1]);
                continue;
            }

            tables[i] = Math.max(tables[i - 2] + nums[i], tables[i - 1]);
        }
        return Math.max(tables[nums.length - 1], tables[nums.length - 2]);

    }


    public static void main(String[] args) {
        int[] num = {2,7,9,3,1};
        System.out.println(new Rob().rob(num));

    }

}