@ 代码随想录算法训练营第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 i=0;i<4;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 i=1;i<pricesSize;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*k+1));
for(int i=0;i<(2*k+1);i++){
dp[i]=(int*)malloc(sizeof(int)*pricesSize);
}
for(int i=0;i<pricesSize;i++){
dp[0][i]=0;
}
for(int i=1;i<=k;i++){
dp[2*i][0]=0;
}
for(int i=0;i<k;i++){
dp[2*i+1][0]=-prices[0];
}
for(int i=1;i<pricesSize;i++){
for(int z=1;z<(2*k+1);z+=2){
dp[z][i]=fmax(dp[z][i-1],dp[z+1][i-1]-prices[i]);
dp[z+1][i]=fmax(dp[z+1][i-1],dp[z][i-1]+prices[i]);
}
}
return dp[2*k][pricesSize-1];
}
题目总结
从2次过度到无数次。
