Day49題目

LeetCode123買賣股票三

核心思想:和昨天的買賣股票相比,這個只允許買兩次,因此把狀態新增幾個,可見代碼注釋

class Solution {public int maxProfit(int[] prices) {// 設置五個狀態  0 : 無操作 , 1 : 第一次買入, 2 : 第一次賣出 , 3: 第二次買入, 4:第二次賣出// 這幾個狀態都是持續性的,表示目前進行到了哪個階段,而不是當前天的動作int[][] dp = new int[prices.length][5];dp[0][0] = 0 ;dp[0][1] = -prices[0];dp[0][2] = 0;dp[0][3] = -prices[0];dp[0][4] = 0;for(int i =  1 ; i < prices.length ; i ++){dp[i][0] = 0;dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]); }return dp[prices.length-1][4];}
}

LeetCode188買賣股票四

核心思想:和上面題目不同的是,你最多可以買K次股票,因此需要有2*k+1個狀態,選擇奇數為買入,偶數為賣出

class Solution {public int maxProfit(int k, int[] prices) {// 奇數為買入// 偶數為賣出int[][] dp = new int[prices.length][2*k+1];for(int i = 1 ; i < 2*k+1 ; i +=2){dp[0][i] = -prices[0]; }for(int i = 1 ; i < prices.length ; i ++){for(int j  = 1; j < 2*k+1;  j +=2  ){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1] - prices[i]);dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);}}return dp[prices.length-1][2*k];}
}