給定一個整數(shù)數(shù)組 prices ，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1：

輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入，在第 2 天 (股票價格 = 4) 的時候賣出，這筆交易所能獲得利潤 = 4-2 = 2 。

代碼

class Solution {public int maxProfit(int k, int[] prices) {if(prices.length==0) return 0;int n=prices.length,res=0;int[][] buy=new int[n][k+1];int[][] sell=new int[n][k+1];buy[0][0]=-prices[0];sell[0][0]=0;for(int i=1;i<=k;i++)//第0天時，不能完成任何交易{sell[0][i]=buy[0][i]=Integer.MIN_VALUE/2;}for(int j=1;j<prices.length;j++){buy[j][0]= Math.max(buy[j-1][0],sell[j-1][0]-prices[j]);for(int i=1;i<=k;i++){buy[j][i]= Math.max(buy[j-1][i],sell[j-1][i]-prices[j]); //上一天買入或者今天買入取最大值sell[j][i]= Math.max(sell[j-1][i],buy[j-1][i-1]+prices[j]); //今天賣出和保持不賣取最大值}}for(int i=1;i<=k;i++)res= Math.max(sell[n-1][i],res);return res;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 188. 买卖股票的最佳时机 IV（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。