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]; }