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卒密。然后我是想了一會(huì)會(huì)兒藻治，就看答案了。。物喷。
碰到DP我是沒自信的『锩洌慌神的钟些，覺得自己肯定做不出來。
仔細(xì)分析下這道題目坯认，以及DP的特性翻擒。
我知道肯定是用 dp[] 來做。但還是想不出來啊牛哺。
當(dāng)時(shí)我的問題是什么陋气？
比如， 10 5 7 30 3 5 8
當(dāng)?shù)竭_(dá)引润，3 時(shí)巩趁，應(yīng)該要去搶，10,30. 但是怎么找的出來呢淳附？怎么把這種結(jié)果保存在dp[] 中呢议慰？事實(shí)上，我現(xiàn)在也是一知半解奴曙。
設(shè)dp[] = new int[nums.length +１];
dp[i] 的含義是： 在[0, i-1] 區(qū)域內(nèi)搶劫别凹，搶劫所得的最大利潤是多少。
那么現(xiàn)在假設(shè)洽糟，dp[0] - dp[i - 1] 都已經(jīng)計(jì)算出來了÷疲現(xiàn)在要計(jì)算dp[i]
那么有兩種情況。即脊框，i- 1家房子有沒有被搶颁督。
第一種，搶了i-1房子浇雹。那么沉御，i - 2他就不能搶了，只能考慮昭灵，[0, i-3]區(qū)域內(nèi)搶劫 + i -1 搶劫吠裆。
money = dp[i - 2] + nums[i - 1];
第二種伐谈，沒搶i - 2房子。那么试疙，就得考慮诵棵，[0, i -2]區(qū)域內(nèi)，怎么搶祝旷，錢才最多履澳。
money = dp[i - 1];
最后比較下大小，取大者怀跛。
dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
這是道典型的DP題距贷。知道了思路感覺也不是很難。但就是想不出來吻谋，而且有畏懼感忠蝗。
**
總結(jié)： 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看來還是有進(jìn)步的漓拾。阁最。。骇两。
一個(gè)簡單的狀態(tài)推導(dǎo)速种。
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];
}
}
想了一會(huì)兒才想出來低千。如果放在面試哟旗，肯定就跪了。
我一直在想栋操， dp[i] 的推導(dǎo)式闸餐。
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
首先肯定會(huì)想到這個(gè)遞推式。然后我的問題是矾芙，
如果 i - 1 那天也正好沒偷舍沙，豈不是我少加了一個(gè) nums[i]。
但后來想想剔宪，這對(duì)結(jié)果不會(huì)造成影響拂铡。
因?yàn)榧词股偎懔耍∽畲笾档臅r(shí)候葱绒，仍然會(huì)拿到這個(gè)值感帅。不會(huì)有影響。
Anyway, Good luck, Richardo! -- 08/25/2016
做 Best Time to Buy and Sell Stock with Cooldown
時(shí)候地淀，想到了還有這種解法失球。具體看那篇文章。
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]);
}
}
