打家劫舍
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,
影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,
如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
现在给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动报警装置的情况下,
能偷窃到的最高金额。
样例输入
[1,2,3,1]
样例输出
4
样例输入
[2,7,9,3,1]
样例输出
12
代码实现
iimport java.util.Arrays;
import java.util.Scanner;
public class dp_3 {
//打家劫舍
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str=sc.nextLine();
if(str.length()==0) {
System.out.println(0);
return;
}
if(str.length()==1) {
System.out.println(str);
return;
}
str=str.substring(1,str.length()-1);
String[] a=str.split(",");
int[] s=Arrays.stream(a).mapToInt(Integer::parseInt).toArray();
int[] dp=new int[a.length];
dp[0]=s[0];
dp[1]=Math.max(dp[0], s[1]);
for (int i = 2; i < a.length; i++) {
dp[i]=Math.max(dp[i-1], dp[i-2]+s[i]);
}
System.out.println(dp[s.length-1]);
}
}