感覺不像股票系列凄诞，倒是很像house rubery那個題似踱。dp function的含義是"
sold[i]:第i天賣掉股票所能獲取的最大利益
hold[i]:第i天穩(wěn)住股票所能獲取的最大利益
轉(zhuǎn)換方程也很好理解：
sold[i] : 今天股票已賣出（不一定是今天賣俯艰，所以用sold)最大利益寺渗，應(yīng)該是一直hold到昨天的最大利益丽惭，再加上今天的賣出價岗仑，減去手續(xù)費跟昨天就賣出的利益取最大值定欧；
hold[i]: 今天保留的最大收益渔呵，可以是一直保留，也可以是昨天賣了砍鸠，今天剛買回來所能產(chǎn)生的最大收益扩氢，兩個取最大。
Follow-up (transition free)
Calculate everytime when prices[i] < prices[i+1] - cost
class Solution {
public int maxProfit(int[] prices, int fee) {
int max = 0;
int[] sold = new int[prices.length]; //not possible
int[] hold = new int[prices.length]; //meaning buy this stock
sold[0] = 0;
hold[0] = -prices[0];
for (int i = 1; i < prices.length; i++){
sell[i] = Math.max(sold[i - 1], hold[i - 1] + prices[i] - fee);
hold[i] = Math.max(hold[i - 1], sold[i - 1] - prices[i]);
}
return Math.max(sold[prices.length - 1], hold[prices.length - 1]);
}
}
optimize to O(1) space (like house rubery a lot)
class Solution {
public int maxProfit(int[] prices, int fee) {
int max = 0;
int sold = 0;
int hold = -prices[0];
for (int i = 1; i < prices.length; i++){
int prevSold = sold;
sold = Math.max(prevSold, hold + prices[i] - fee);
hold = Math.max(hold, prevSold - prices[i]);
}
return Math.max(sold, hold);
}
}
