东莞常平做网站,抖音开放平台是什么,传媒公司排行,网站的备案手续文章目录题目描述思路 代码更新版题目描述
好家伙#xff0c;真是一道不符合社会主义价值观的题目不过我们还是要把这道题做了#xff0c;而且还得用上动态规划
思路 代码
首先#xff0c;不能打劫相邻然后#xff0c;房屋都是非负整数#xff08;讲道理 代码更新版题目描述
好家伙真是一道不符合社会主义价值观的题目不过我们还是要把这道题做了而且还得用上动态规划
思路 代码
首先不能打劫相邻然后房屋都是非负整数讲道理之后不会出个带负数的版本把。。老恶心人了开始做吧用dp直接冲
因为dp需要初始化前三个数因此把这三个数作为特殊情况先判断然后考虑到第n个值肯定在第n-2和第n-3个值之间取第n-1不能取第n-4还不如直接取n-2以此类推。更多信息见注释
class Solution {public int rob(int[] nums) {int len nums.length;// 三种特殊情况if(len 0){return 0;}if(len 1){return nums[0];}if(len 2){return Math.max(nums[1],nums[0]);}// dp[i]以偷nums[i]结尾的情况能得到的最大钱数int[] dp new int[len];// dp的初始化这三个值是固定的。dp[0] nums[0];dp[1] nums[1];dp[2] nums[0] nums[2];for(int i3;ilen;i){// 中间隔着一个 nums[i-1]防报警就在这里实现dp[i] Math.max(dp[i-2],dp[i-3]) nums[i];}// 最大值要么是倒数第一家要么是倒数第二家return Math.max(dp[len-1],dp[len-2]);}
}更新版
我以前咋写代码这么乱。。
class Solution {public int rob(int[] nums) {if(nums.length 1) {return nums[0];}int[] dp new int[nums.length];dp[0] nums[0];dp[1] Math.max(nums[1], nums[0]);for(int i 2; i nums.length; i) {dp[i] Math.max(dp[i - 2] nums[i], dp[i - 1]);}return dp[nums.length - 1];}
}
