网站的产品中心怎么做,宽屏大气网站模板,东莞网络做推广公司,在线手机动画网站模板Problem: 198. 打家劫舍 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 1.构建多阶段决策模型#xff1a;n个房屋对应n个阶段#xff0c;每一个阶段决定一个房间是偷还是不偷#xff0c;两种决策#xff1a;偷、不偷 2.定义状态#xff1a;不能记录每个阶段决策… Problem: 198. 打家劫舍 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 1.构建多阶段决策模型n个房屋对应n个阶段每一个阶段决定一个房间是偷还是不偷两种决策偷、不偷 2.定义状态不能记录每个阶段决策完之后小偷可偷的最大金额需要记录不同决策对应的最大金额也就是这个房屋偷-对应的最大金额这个房屋不偷-对应的最大金额。int[n][2]记录每个阶段的状态dp[i][0]表示第i个物品不偷当下剩余的最大金额dp[i][1]表示第i个物品偷当下剩余的最大金额 3.定义状态转移方程dp[i][0] max(dp[i - 1][0], dp[i - 1][1])即表示假设不偷则当前阶段可以获得的最大值为上一个房屋偷或者不偷的二者中的最大金额dp[i][1] dp[i - 1][0] nums[i]即表示假设当前阶段偷则当前可以获得的最大金额为上一个房屋不偷加上当前当前房屋的金额 解题方法 1.获取nums数组的长度为n并定义int类型数组dpint[][] dp new int[n][2]; 2.初始化dp[0][0]为0dp[0][1]为nums[0]; 3.完成动态转移方程 4.返回max(dp[n - 1][0], dp[n - 1][1]) 复杂度
时间复杂度: O ( n ) O(n) O(n);其中 n n n为数组nums的长度 空间复杂度: O ( n ) O(n) O(n) Code
class Solution {/*** Get the maximum amount** param nums Given array(Store the amount of each house)* return int*/public int rob(int[] nums) {if (nums.length 0) {return 0;}int n nums.length;int[][] dp new int[n][2];//dp[i][0] represents the maximum amount// that can currently be obtained without stealingdp[0][0] 0;//dp[i][1] represents the maximum amount// that can be obtained when not stealingdp[0][1] nums[0];for (int i 1; i n; i) {dp[i][0] Math.max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] dp[i - 1][0] nums[i];}return Math.max(dp[n - 1][0], dp[n - 1][1]);}
}
