My code:
public class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int n = prices.length;
int[] s0 = new int[n];
int[] s1 = new int[n];
int[] s2 = new int[n];
s0[0] = 0;
s1[0] = -prices[0];
s2[0] = Integer.MIN_VALUE;
for (int i = 1; i < n; i++) {
s0[i] = Math.max(s0[i - 1], s2[i - 1]);
s1[i] = Math.max(s0[i - 1] - prices[i], s1[i - 1]);
s2[i] = s1[i - 1] + prices[i];
}
return Math.max(s0[n - 1], Math.max(s1[n - 1], s2[n - 1]));
}
}
reference:
https://discuss.leetcode.com/topic/30680/share-my-dp-solution-by-state-machine-thinking/2
这道题目看了解释后才做出来。我觉得上面的解释说的很好。
这是一种新的DP类型。通过画 状态机来解决问题。
状态机画出来后，问题也就解决了。
只需要处理一些 corner case。
这道题目很像那个 robber 的题。他也是不能连续的偷。但是他是累加，这个有个买卖的先后关系，所以更难。
那道题目就两个状态。
s0 s1
s0 --> rest s0
s0 --> steal s1
s1 --> rest s0
s0[i] = max(s0[i - 1], s1[i - 1]);
s1[i] = s0[i - 1] + money[i];
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]);
}
}
Anyway, Good luck, Richardo! -- 08/26/2016
