感觉不像股票系列，倒是很像house rubery那个题。dp function的含义是"
sold[i]:第i天卖掉股票所能获取的最大利益
hold[i]:第i天稳住股票所能获取的最大利益
转换方程也很好理解：
sold[i] : 今天股票已卖出（不一定是今天卖，所以用sold)最大利益，应该是一直hold到昨天的最大利益，再加上今天的卖出价，减去手续费跟昨天就卖出的利益取最大值；
hold[i]: 今天保留的最大收益，可以是一直保留，也可以是昨天卖了，今天刚买回来所能产生的最大收益，两个取最大。
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);
}
}
