java之 ------------[LeetCode] House Robber 打家劫舍

刚开始做这一道题感觉卧槽，这不简单吗，直接去把数组下标和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];
}