做网站公司名字应该用图片吗,技术支持 鼎维重庆网站建设专家,wordpress入门到精通,大气个人网站源码题目
一条环形街道上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取的财产的数量。例如#xff0c;街道上5家的财产用数组[2#xff0c;3#xff0c;4#xff0c;5…题目
一条环形街道上有若干房屋。输入一个数组表示该条街道上的房屋内财产的数量。如果这条街道上相邻的两幢房屋被盗就会自动触发报警系统。请计算小偷在这条街道上最多能偷取的财产的数量。例如街道上5家的财产用数组[23453]表示如果小偷到下标为1和3的房屋内盗窃那么他能偷取到价值为8的财物这是他在不触发报警系统的情况下能偷取到的最多的财物
分析
由于这个问题和面试题89的区别在于小偷不能同时到标号为0和n-1的两幢房屋内偷东西。如果他考虑去标号为0的房屋那么他一定不能去标号为n-1的房屋如果他考虑去标号为n-1的房屋那么他一定不能去标号为0的房屋。因此可以将这个问题分解成两个子问题一个问题是求小偷从标号为0开始到标号为n-2结束的房屋内能偷得的最多财物数量另一个问题是求小偷从标号为1开始到标号为n-1结束的房屋内能偷得的最多财物数量。小偷从标号为0开始到标号为n-1结束的房屋内能偷得的最多财物数量是这两个子问题的解的最大值。
解
public class Test {public static void main(String[] args) {int[] cost {2, 3, 4, 5, 3};int result rob(cost);System.out.println(result);}public static int rob(int[] nums) {if (nums.length 0) {return 0;}if (nums.length 1) {return nums[0];}int result1 helper(nums, 0, nums.length - 2);int result2 helper(nums, 1, nums.length - 1);return Math.max(result1, result2);}private static int helper(int[] nums, int start, int end) {int[] dp new int[2];dp[0] nums[start];if (start end) {dp[1] Math.max(nums[start], nums[start 1]);}for (int i start 2; i end; i) {int j i - start;dp[j % 2] Math.max(dp[(j - 1) % 2], dp[(j - 2) % 2] nums[i]);}return dp[(end - start) % 2];}}
