外贸品牌网站设计,德州手机网站建设电话,军事新闻,wordpress 教程状态分类#xff1a; f[i,j,0]考虑前i只股票#xff0c;进行了j笔交易#xff0c;目前未持有股票 所能获得最大利润 f[i,j,1]考虑前i只股票#xff0c;进行了j笔交易#xff0c;目前持有股票 所能获得最大利润 状态转移#xff1a; f[i][j][0] Math.max(f[i-1][j][0],f[… 状态分类 f[i,j,0]考虑前i只股票进行了j笔交易目前未持有股票 所能获得最大利润 f[i,j,1]考虑前i只股票进行了j笔交易目前持有股票 所能获得最大利润 状态转移 f[i][j][0] Math.max(f[i-1][j][0],f[i-1][j][1]prices[i]); f[i][j][1] Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i]); class Solution {static int INF 0x3f3f3f3f;public int maxProfit(int k, int[] prices) {int n prices.length;int f[][][] new int[n1][k1][2];for(int i 0;i n;i){for(int j 0;j k;j){Arrays.fill(f[i][j],-INF);}}for(int i 0;i n;i)f[i][0][0] 0;for(int i 1;i n;i){for(int j 1;j k;j){f[i][j][0] Math.max(f[i-1][j][0],f[i-1][j][1]prices[i-1]);f[i][j][1] Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);}}int ans 0;for(int i 0;i k;i){ans Math.max(ans,f[n][i][0]);}return ans;}
} 还有一位大佬的看不懂的极妙解法--滚动的dp
// java
class Solution {public int maxProfit(int k, int[] prices) {int[] buy new int[k], sell new int[k];Arrays.fill(buy, -prices[0]);for (int i 1; i prices.length; i) {for (int j 0, pre 0; j k; j) {buy[j] (pre Math.max(buy[j], pre - prices[i]));sell[j] (pre Math.max(sell[j], pre prices[i]));}}return Math.max(sell[k - 1], 0);}
}
