脚本宝典收集整理的这篇文章主要介绍了Leecode no.198. 打家劫舍,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
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)); }}
以上是脚本宝典为你收集整理的Leecode no.198. 打家劫舍全部内容,希望文章能够帮你解决Leecode no.198. 打家劫舍所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。