时间戳

首页 > 解决方案 > 动态规划

java - 动态规划

问题描述

一个小镇有N条街道，每条街道有一个宝库，里面有一定数量的金币-C(1)....C(N)。由于强盗很聪明，为了不被抓住，如果他在给定街道的房子里抢劫，他不会在与被抢劫房子相邻的两条街道上的房子里抢劫（无论是左边还是右边）。因此，他避免了人们的意识，并且降低了他的风险。给定 N 和每个宝库中的硬币 C(i)（其中 i=1 到 N），求出盗贼最多可以获得的金币 M。

import java.util.Scanner;

public class MaximiseRobbery {

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  int houses = scan.nextInt();
  int[] amPerHouse = new int[houses];
  for (int i = 0; i < houses; i++) {
   amPerHouse[i] = scan.nextInt();
  }
  int maximumRobbery = maximizeRobbery(amPerHouse, houses);
  System.out.println(maximumRobbery);
  scan.close();
 }

 private static int maximizeRobbery(int[] amPerHouse, int houses) {
  if (houses == 1) {
   return amPerHouse[0];
  } else if (houses == 2) {
   return Math.max(amPerHouse[0], amPerHouse[1]);
  }
  int[] dp = new int[amPerHouse.length];
  dp[0] = amPerHouse[0];
  dp[1] = amPerHouse[1];
  for (int i = 2; i < houses; i++) {
   dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);
  }
  return dp[houses - 1];
 }
}

输入：

7
10 20 15 1 9 12 5

输出：

32

但根据上述实现，得到的输出是 39

也用于输入：

10
5 6 6 16 30 15 13 16 19 27

输出：

63

但根据上面的实现，得到的输出是 84

标签： javadynamic

解决方案

我认为您没有正确理解该声明。它说的是，IMO，如果你抢劫街道上的房子，i你就不能抢劫左边 2 条街道上的房子，soi-1和i-2，以及右边 2 条街道上的房子，soi+1和i+2。根据这个修改应该可以工作。实际上，在第一个示例中，被抢劫的房屋都在索引中1，5因此sum = 20 + 12 = 32。

推荐阅读