做代理网站,蓬莱市建设局网站,中高端网站建设,网站建设策划稿代码随想录算法训练营第8周#xff08;C语言#xff09;|Day54#xff08;动态规划#xff09;
Day53、动态规划#xff08;包含题目 ● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV #xff09;
123.买卖股票的最佳时机III
题目描述
给定一个数组#… 代码随想录算法训练营第8周C语言|Day54动态规划
Day53、动态规划包含题目 ● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV
123.买卖股票的最佳时机III
题目描述
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
题目解答
int maxProfit(int* prices, int pricesSize) {int **dp(int**)malloc(sizeof(int*)*4);for(int i0;i4;i){dp[i](int*)malloc(sizeof(int)*pricesSize);}dp[0][0]-prices[0];//第一次持有dp[1][0]0;//第一次不持有dp[2][0]-prices[0];//第二次持有dp[3][0]0;for(int i1;ipricesSize;i){dp[0][i]fmax(dp[0][i-1],-prices[i]);dp[1][i]fmax(dp[1][i-1],dp[0][i-1]prices[i]);dp[2][i]fmax(dp[2][i-1],dp[1][i-1]-prices[i]);dp[3][i]fmax(dp[3][i-1],dp[2][i-1]prices[i]);}return dp[3][pricesSize-1];
}题目总结
买两次的股票问题。
188.买卖股票的最佳时机IV
题目描述
给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
题目解答
int maxProfit(int k, int* prices, int pricesSize) {int **dp(int**)malloc(sizeof(int*)*(2*k1));for(int i0;i(2*k1);i){dp[i](int*)malloc(sizeof(int)*pricesSize);}for(int i0;ipricesSize;i){dp[0][i]0;}for(int i1;ik;i){dp[2*i][0]0;}for(int i0;ik;i){dp[2*i1][0]-prices[0];}for(int i1;ipricesSize;i){for(int z1;z(2*k1);z2){dp[z][i]fmax(dp[z][i-1],dp[z1][i-1]-prices[i]);dp[z1][i]fmax(dp[z1][i-1],dp[z][i-1]prices[i]);}}return dp[2*k][pricesSize-1];}题目总结
从2次过度到无数次。
