题目1——打家劫舍一
你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
给定一个整数数组nums，数组中的元素表示每个房间存有的现金余额，请你计算在不被发现的前提下最多的偷窃金额。
示例
输入：[1,2,3,4]
输出：6(最优方案是偷第2、4个房间)
解题思路
贪心算法和动态规划的共同点是：两者都具有最优子结构性质，即问题的最优解中包含子问题的最优解。
两者的不同点是：
动态规划中，每步做出的选择往往依赖于相关子问题的解，因而只有在解除相关子问题时才能做出选择。
而贪心算法中，仅在当前状态下做出最好选择，然后再去解这个选择做出后产生的子问题。
如果利用贪心算法偷钱，为了偷取更多的钱，可能会连续放弃两家不偷，因此这种方法不可行，考虑利用动态规划来解决。对于每一个人家，可选择偷或者不偷，状态转移方程为dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1)。
代码实现
import java.util.*;
public class Solution {
public int rob (int[] nums) {
int n = nums.length;
if(n == 1)
return nums[0];
int[] dp = new int[n+1];
dp[1] = nums[0];
for(int i=2;i<=n;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[n];
}
}
题目2——打家劫舍二
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即偷了第一家，就不能偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
示例
输入：[1,3,6]
输出：6(1和3相邻，因此最优方案是偷第3个房间)
解题思路
与题目一类似，只是这道题是环形，第一家和最后一家相邻，不能同时取到，所以可分为两种情况：偷第一家，则最后一家不能偷；偷最后一家，则第一家不能偷。除去考虑这些，其他家与第一题做法相同。
最后取两种情况中最大的值即可。
代码实现
import java.util.*;
public class Solution {
public int rob (int[] nums) {
int n = nums.length;
if(n == 1)
return nums[0];
int[] dp = new int[n+1];
dp[1] = nums[0];
for(int i=2;i<n;i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
}
int res = dp[n-1];
Arrays.fill(dp,0);
for(int i=2;i<=n;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
return Math.max(res,dp[n]);
}
}
|