leetcode第188題，買賣股票4
DP思考過程：首先總結出有哪些狀態，例如這題中，k代表交易次數，所有prices數組中每個元素都會有2k個狀態(即（買+賣)k=2k),所以此時我們可以創建一個2k長度的數組作為記錄，接下來分析狀態轉移
可以輕易想到buy=上一次sell的錢-prices[i];//這里注意第一次交易時sell=0;
sell=上一次buy的錢+prices[i];
這里leetcode有個坑，內存溢出問題，當2k很大時，這時的數組會非常大，導致內存溢出，優化方式：當2*k>=prices.length時，其實這時就是買賣股票2的情況，即無限次交易
好了，分析完了，接下來代碼過程
看不懂的可以留言或者私聊我

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if(prices==null||prices.length<2||k<1)return 0;
        //當2*k>=prices.length時，優化為maxPRofit2方法
        if(2*k>=n)return maxProfit2(prices,n);
        return maxProfit1(k,prices,n);
    }
    public int maxProfit1(int k,int[] prices,int n){
		int[] memo = new int[2 * k];
		for (int i = 0; i < k; i++) {
			memo[2 * i] = Integer.MIN_VALUE;
		}
		for (int i = 0; i < n; i++) {
		   //記錄每個memo中的值以便 i++后使用
			for (int j = 0; j < 2 * k; j++) {
				if ((j & 1) == 0)//偶數為buy
					memo[j] = Math.max(memo[j], j == 0? -prices[i]	: memo[j - 1] - prices[i]);
				else  //奇數為sell
					memo[j] = Math.max(memo[j], memo[j - 1] + prices[i]);
			}
		}
		return memo[2 * k - 1];
    }
    private int maxProfit2(int[] prices,int n) {
		int buy[]=new int[n];
		int sell[]=new int[n];
		buy[0]=-prices[0];
		sell[0]=0;
		for(int i=1;i<n;i++){
			buy[i]=Math.max(buy[i-1], sell[i-1]-prices[i]);
			sell[i]=Math.max(sell[i-1], buy[i-1]+prices[i]);
		}
		return sell[n-1];
	}
}