淄博市沂源县建设局网站,漳州台商投资建设局网站,西部数码网站模板,网易做网站198.你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。 给定一个代表每个房屋存放金额… 198.你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 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 。 我的原始人解法首先试一下分成一个个子问题很容易想到的是偷到 1 号房屋为止的最高金额偷到 2 号房屋为止的最高金额… 那么就有 f[i] 为偷到最后一个房屋为 i 时的最高金额(不一定就偷了 i 房屋只是范围到 i 为止)接着找关联性注意限制条件不能偷连续的房屋首先 f[0] 只能偷房屋 1就直接为 nums[0] 接着 f[1] 开始有说法了两个房屋我要么偷了前一个这个不偷了要么前一个没偷我偷这个两者我取最大值所以为 max(f[0],nums[1]), f[2] 同理 f[2] 也是两种可能如果我偷了前一个房屋那么我这个房屋是肯定不能偷了也就是说我只能是 f[2-1]而如果我前一天没偷那么我今天必偷无疑也就是 f[2-2] nums[2]两者之中我取最大的可能性即可以此类推这也就得到了状态转移方程和初始值。为了方便我定义数组时长度加了 1表示第一天的时候前一天(逻辑上不存在所以正好为 0)不偷的金额为 0偷则为 nums[0]。 public int rob(int[] nums) {int m nums.length;int[] f new int[m1];f[1] nums[0];for(int i2; im; i){f[i] Math.max(f[i-1],f[i-2]nums[i-1]);}return f[m];}由于我们只需要知道前一天偷或不偷所以定义两个变量滚动更新记录就足够了不需要数组 int m nums.length;int x10,x2nums[0];for(int i2; im; i){int temp Math.max(x2,x1nums[i-1]);x1 x2;x2 temp;}return Math.max(x1,x2);他人题解我就不看了
