题解 | #打家劫舍(一)#
打家劫舍(一)
http://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79
一、思路
动态规划:
- 确定属性:表示从数组下标为的房间开始到达数组下标为的房间此时所能获得的最多的偷窃金额。
- 确定边界条件:
- 确定状态转移方程:
- 确定结果值:假定为数组的长度,即为从数组下标为的房间开始到达数组下标为的房间此时所能获得的最多的偷窃金额。也就是题目要求的,因此我们最后返回即可。
二、代码
初步代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int rob (int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}
}
此时时间复杂度是,空间复杂度是
优化后的代码
我们可以发现只跟之前两次的状态有关,因此我们可以不用创建空间的复杂度,可以用滚动数组代替,优化空间复杂度为
代码
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型
*/
public int rob (int[] nums) {
// write code here
int n = nums.length;
if (n == 1) {
return nums[0];
}
int a = nums[0];
int b = Math.max(nums[0], nums[1]);
int sum = 0;
for (int i = 2; i < n; i++) {
int tmp = b;
b = Math.max(a + nums[i], b);
a = tmp;
}
return b;
}
}
++代码
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int rob(vector<int>& nums) {
// write code here
int n = nums.size();
if (n == 1) {
return nums[0];
}
int a = nums[0];
int b = max(nums[0], nums[1]);
for (int i = 2 ; i < n; i++) {
int tmp = b;
b = max(nums[i] + a, b);
a = tmp;
}
return b;
}
};
代码
class Solution:
def rob(self , nums: List[int]) -> int:
# write code here
n = len(nums)
if n == 1:
return nums[0]
a = nums[0]
b = max(nums[0], nums[1])
for i in range(2, n):
tmp = b
b = max(nums[i] + a, b)
a = tmp
return b;