leetcode 198题目
给定一个数组(不同权重(钱)的店家),强盗可以抢不相邻的店家,求最大的钱数。
- 暴力搜索
- 代码
public class HouseRobber {
public int rob(int[] nums) {
//return solve(nums.length-1 ,nums);
return solve(0 ,nums);
}
private int solve(int idx, int[] nums) {
if(idx > nums.length-1){
return 0;
}
return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
}
}
solve(int idx, int[] nums):抢下标为idx的店,最大的钱数。
return Math.max(solve(idx+1,nums),solve(idx+2,nums) + nums[idx]);
对于idx的店家只有两种可能:
- 抢idx的话
solve(idx+2,nums) + nums[idx]
- 不抢idx的话
solve(idx+1,nums)
结果:超时!
原因:
-
n->(n-2,n-3,n-4) 状态n由前n-2个状态决定 前n-2个状态每个都要算一遍
-
n-1->(n-3,n-4,n-5) 状态n-1由前n-3个状态决定 前n-3个状态每个都要算一遍
大量的重复运算,导致时间复杂度剧增,需要存储已经计算过的状态来解决这个问题
- 改进
private static int[] res = null;
public static int rob(int[] nums) {
res = new int[nums.length];
for (int i = 0; i < res.length; i++) {
res[i] = -1 ;
}
return solve(0, nums);
}
private static int solve(int idx, int[] nums) {
if (idx > nums.length - 1) {
return 0;
}
if (res[idx] >= 0 ) {
return res[idx];
}
res[idx] = Math.max(solve(idx + 1, nums), solve(idx + 2, nums) + nums[idx]);
return res[idx];
}
用res数组来记录已经计算过的状态
if (res[idx] >= 0 ) { return res[idx]; }
计算过的话,直接返回,去除冗余计算。
动态规划
public class HouseRobber {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length]; //记录抢到某个下标时的最优解
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[dp.length - 1];
}
}
- 实质:递归
- 最优子结构
- 子问题最优决策可以导出原问题的最优决策
- 无后效性:抢了第n家店之后,后面的n-1家店不能抢(影响到了后面的决策);而这里进入了n-2,跳过了n-1,。
- 重叠子问题
- 去冗余
- 空间换时间
网友评论