动态规划-入室抢劫-一排

package com.algorithm.dynamicprogramming;/*** 你是一名职业抢劫犯，计划抢劫街道两旁的房屋。每家都有一定数量的钱。* 这个地方所有的房子都排成一个排。同时，相邻房屋已连接安全系统，* 如果两个相邻房屋在同一晚被闯入，它将自动联系警方。* 给出一个非负整数列表，表示每家每户的金额，确定今晚在不报警的情况下可以抢劫的最大金额。* * Example 1:* Input [1,3,1] Output 3* * Example 2:* Input [2,3,2] Output 4* * Example 3:* Input [1,2,3,2] Output 4* @author rich**/
public class HouseRobber {public static void main(String[] args) {int[] arrs = new int[] {1,11,3,2,5};System.out.println(houseRobber(arrs));}/*** 算法分析：* 当 n = 1 return arrs[n]* 当 n = 2 return Math.max( arrs[0],  arrs[1])* 当 n > 3 * memo[0] = arrs[0]* memo[1] = arrs[1]* memo[i] = Math.max(memo[i-2]+arrs[i], memo[i-1]);* @param arrs* @return*/public static int houseRobber(int[] arrs) {int n = arrs.length;if (n == 1) return arrs[n];if (n == 2) return Math.max( arrs[0],  arrs[1]);int[] memo = new int[arrs.length+1];memo[0] = arrs[0];memo[1] = arrs[1];for (int i = 2;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！