My code:
import java.util.Arrays;
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
Arrays.sort(dp);
return dp[dp.length - 1];
}
}
My test result:
这道题目是DP。然后我是想了一会会儿，就看答案了。。。
碰到DP我是没自信的。慌神的，觉得自己肯定做不出来。
仔细分析下这道题目，以及DP的特性。
我知道肯定是用 dp[] 来做。但还是想不出来啊。
当时我的问题是什么？
比如， 10 5 7 30 3 5 8
当到达，3 时，应该要去抢，10,30. 但是怎么找的出来呢？怎么把这种结果保存在dp[] 中呢？事实上，我现在也是一知半解。
设dp[] = new int[nums.length +１];
dp[i] 的含义是： 在[0, i-1] 区域内抢劫，抢劫所得的最大利润是多少。
那么现在假设，dp[0] - dp[i - 1] 都已经计算出来了。现在要计算dp[i]
那么有两种情况。即，i- 1家房子有没有被抢。
第一种，抢了i-1房子。那么，i - 2他就不能抢了，只能考虑，[0, i-3]区域内抢劫 + i -1 抢劫。
money = dp[i - 2] + nums[i - 1];
第二种，没抢i - 2房子。那么，就得考虑，[0, i -2]区域内，怎么抢，钱才最多。
money = dp[i - 1];
最后比较下大小，取大者。
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
这是道典型的DP题。知道了思路感觉也不是很难。但就是想不出来，而且有畏惧感。
**
总结： DP
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0)
return 0;
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]);
if (n <= 2)
return dp[n - 1];
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[n - 1];
}
}
这次是我自己做出来的。
练了一些DP看来还是有进步的。。。。
一个简单的状态推导。
dp[i] 可能被dp[i - 1] and dp[i - 2] 影响。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
else if (nums.length == 1) {
return nums[0];
}
int n = nums.length;
int[] dp = new int[n];
// dp[i] means the maximum money after ith house
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
}
return dp[n - 1];
}
}
想了一会儿才想出来。如果放在面试，肯定就跪了。
我一直在想， dp[i] 的推导式。
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
首先肯定会想到这个递推式。然后我的问题是，
如果 i - 1 那天也正好没偷，岂不是我少加了一个 nums[i]。
但后来想想，这对结果不会造成影响。
因为即使少算了，取最大值的时候，仍然会拿到这个值。不会有影响。
Anyway, Good luck, Richardo! -- 08/25/2016
做 Best Time to Buy and Sell Stock with Cooldown
时候，想到了还有这种解法。具体看那篇文章。
My code:
public class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
else if (nums.length == 1) {
return nums[0];
}
int n = nums.length;
int[] s0 = new int[n + 1];
int[] s1 = new int[n + 1];
s0[0] = 0;
s1[0] = 0;
for (int i = 1; i <= n; i++) {
s0[i] = Math.max(s0[i - 1], s1[i - 1]);
s1[i] = s0[i - 1] + nums[i - 1];
}
return Math.max(s0[n], s1[n]);
}
}
