[LeetCode] House Robber 打家劫舍

- 日理万妓 2022-05-18 02:57 183阅读 0赞

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警**。

给定一个代表每个房屋存放金额的非负整数数组，计算你**在不触动警报装置的情况下，**能够偷窃到的最高金额。

**示例 1:**

输入: [1,2,3,1]
    输出: 4
    解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
         偷窃到的最高金额 = 1 + 3 = 4 。

**示例 2:**

输入: [2,7,9,3,1]
    输出: 12
    解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
         偷窃到的最高金额 = 2 + 9 + 1 = 12 。

**刚开始做这一道题感觉卧槽，这不简单吗，直接去把数组下标和2取余的数相加再把剩下的数相加，比较这两个和谁大就输出谁，不就行了，但是啊，我操，事实证明，我还是太天真了，我操出现\[2,1,1,2\]这种情况，我当时还怀疑为什么那么简单后来一想，我操，这不是动态规划吗，于是乎，恶补一下怎么实现动态规划的，说白了，动态规划就是把大的数据拆成小的数据，如我想计算f(10),我就要计算出f(9)+1,然后我想计算出f(9)=f(8)+1，递推的方式直到f(1)=f(0)+1,就结束了。就是上面的结果依赖与下边的结果。**

/* 注意这里的返回值，你一定在疑惑为什么返回值，返回的是arry.length-1，那是因为我刚开始计算的时候
    *  就涉及到前三个数字，如果返回arry.length，那么会报越界异常。
    *  其实啊，说白了，就是【表情】那个对一个数组的递推，只不过借助一个空的数组来实现
    *  前期给【表情】【表情】这个空的数组赋初值，这里是两个，借助的这个数组就前两个是有值的，其它没值
    * */
    public int leastPath(int[] arry) {
        int length = arry.length;
        // 声明一个空的数组，就是为了递推做准备
        int[] another = new int[arry.length];
        if (length == 0) {
            return 0;
        }
    
        if (length == 1) {
            return arry[0];
        }
    
        int many = Math.max(arry[0],arry[1]);
        if (length == 2) {
            return many;
        }
        // 设置要进行递推的初值
        another[0] = arry[0];
        another[1] = many;
        // 注意这里的another.length，的设置，注意长度和下标的区别
        for (int i = 2; i <another.length ; i++) {
            // 这是最核心的代码，当你计算出第一步递推，后边就简单了
            another[i] = Math.max(another[i-2]+arry[i],arry[i-1]);
        }
        return another[arry.length-1];
    }