南昌餐厅网站建设,网站负责人备案采集照,网站主要的设计内容主题,口碑好的福州网站建设你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个房屋存放金额的…你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你在不触动警报装置的情况下能够偷窃到的最高金额。
示例 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 。
思路动态规划
dp[n] max(dp[n-1],dp[n-2]nums[n]);
提交的代码
class Solution { public int rob(int[] nums) { int i; int n nums.length; if(n0) { return 0; } int[] dp new int[n]; if(n1) { return nums[0]; } dp[0] nums[0]; dp[1] java.lang.Math.max(dp[0], nums[1]); for(i2;in;i) { dp[i] java.lang.Math.max(dp[i-1], dp[i-2]nums[i]); } return dp[n-1]; } }
完整代码 public class Solution198 { public static int rob(int[] nums) { int i; int n nums.length; if(n0) { return 0; } int[] dp new int[n]; if(n1) { return nums[0]; } dp[0] nums[0]; dp[1] java.lang.Math.max(dp[0], nums[1]); for(i2;in;i) { dp[i] java.lang.Math.max(dp[i-1], dp[i-2]nums[i]); } return dp[n-1]; } public static void main(String[] args) { int[] nums {2,7,9,3,1}; System.out.println(rob(nums)); } }
