怀柔手机网站建设,装修设计软件网页版,网站品牌推广公司,百度竞价排名事件题意理解#xff1a; 给你一个整数数组 prices 和一个整数 k #xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说#xff0c;你最多可以买 k 次#xff0c;卖 k 次。 注意#xf… 题意理解 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 这道题的特别之处是最多可以买卖k次k是一个可以变化的值所以使用j对k的数值进行遍历。 解题思路 1定义dp二维[][]数组 dp[0][0]表示不操作 dp[i][j2(k-1)1]表示第k次买入 dp[i][j2(k-1)2]表示第k次卖出 (2) 初始化 dp[0][0]0 dp[0][j2(k-1)1]-prices[i] dp[0][j2(k-1)2]0 (3) 递推公式 dp[i][j2(k-1)1] max(延续之前状态买入) max(dp[i-][j2(k-1)1],dp[i-1][j2(k-1)]-prices[i]) dp[i][j2(k-1)2]-prices[i] max(延续之前状态卖出) max(dp[i-][j2(k-1)2],dp[0-1][j2(k-1)1]prices[i]) 1.解题
public int maxProfit(int k, int[] prices) {int[][] dpnew int[prices.length][2*k1];for(int i0;i2*k;i){if(i%20)dp[0][i]0;else dp[0][i]-1*prices[0];}for(int i1;iprices.length;i){dp[i][0]dp[i-1][0];for(int j0;j2*k;j2){dp[i][j1]Math.max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2]Math.max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}int max0;for(int i0;i2*k;i)maxMath.max(max,dp[prices.length-1][i]);return max;}
2.分析 时间复杂度O(kn) 空间复杂度O(2kn)
