@ 代码随想录算法训练营第8周（C语言）|Day54（动态规划）

@ 代码随想录算法训练营第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次过度到无数次。