//打家劫舍
/*
* 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是
* 相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
* 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下,一夜之内能够偷窃到的最高金额
* */
public class P47 {
public static void main(String[] args) {
// int[] nums = new int[]{1,2,3,1}; //4
int[] nums = new int[]{2,7,9,3,1}; //12
System.out.println(maxMoney(nums, nums.length-1));
System.out.println(maxMoney2(nums));
System.out.println(maxMoney3(nums));
}
//递归
public static int maxMoney(int[] nums, int index){
if(nums == null || index < 0){ //递归出口
return 0;
}
if(index == 0){
return nums[0];
}
//递推公式,i-1 和 i-2+nums[i]的最优解
return Math.max(maxMoney(nums, index-1), maxMoney(nums, index-2)+nums[index]);
}
//存在重复计算,左边会递归i-1,i-2,i-3,右边也同样i-2、i-3...
//把递归的陪一次记录存起来,就是动态规划中的DP数组
//用递归就是dp有值得时候直接取,没值得时候递归,就避免重复递归的问题
//动态规划-迭代(不用递归)
public static int maxMoney2(int[] nums){
int length = nums.length;
if(nums == null || length == 0){
return 0;
}
if(length == 1){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
//有了0和1这两个数,就可以推断其他数
//迭代
for(int i=2; i<length; i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]); //递推公式
}
return dp[length-1]; //最后位置就是最优解
}
//上面的方法占用空间复杂度高,有些数据存起来但又不使用
//优化
public static int maxMoney3(int[] nums){
int length = nums.length;
if(nums == null || length == 0){
return 0;
}
if(length == 1){
return nums[0];
}
int first = nums[0];
int second = nums[1];
for(int i=2; i<length; i++){
int temp = second;
second = Math.max(first+nums[i], second);
first = temp;
}
return second;
}
}
网友评论