本文主要是介绍LeetCode 123买卖股票的最佳时机-iii 188买卖股票的最佳时机-iv | 代码随想录25期训练营day50,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
动态规划算法8
LeetCode 123 买卖股票的最佳时机-iii 2023.12.13
- 题目链接
- 代码随想录讲解[链接]
int maxProfit(vector<int>& prices) {//1确定dp二维数组//dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入//dp[i][2]表示遍历到第i天时第二次持有股票的当前收入;dp[i][3]表示遍历到第i天时第二次未持有股票的当前收入vector<vector<int>> dp(prices.size(), vector<int>(4, 0));//3初始化,第一天第一次与第二次持有股票的收入为-prices[0],其他值为0dp[0][0] = -prices[0];dp[0][2] = -prices[0];//2确定递推公式,4确定遍历顺序for (int i = 1; i < prices.size(); i++){//第i天第一次持有股票的收入=max(股票不卖(上一天第一次持有股票的收入),第一次买完今天的股票的收入)dp[i][0] = max(dp[i-1][0], -prices[i]);//第i天第一次未持有股票的收入=max(上一天第一次未持有股票的收入,今天第一次卖股票的收入)dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]);//第i天第二次持有股票的收入=max(股票不卖(上一天第二次持有股票的收入),第二次买完今天的股票的收入)dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i]);//第i天第二次未持有股票的收入=max(上一天第二次未持有股票的收入,今天第二次卖股票的收入)dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i]);}//输出答案为最后一天第二次未持有股票的结果return dp[prices.size()-1][3];
}
LeetCode 188 买卖股票的最佳时机-iv 2023.12.13
- 题目链接
- 代码随想录讲解[链接]
int maxProfit(int k, vector<int>& prices) {//1确定dp二维数组//dp[i][0]表示遍历到第i天时第一次持有股票的当前收入;dp[i][1]表示遍历到第i天时第一次未持有股票的当前收入//dp[i][2*j]表示遍历到第i天时第j+1次持有股票的当前收入;dp[i][2*j+1]表示遍历到第i天时第j+1次未持有股票的当前收入vector<vector<int>> dp(prices.size(), vector<int>(2*k, 0));//3初始化,第一天第一次到第k次持有股票的收入为-prices[0],其他值为0for (int i = 0; i < 2*k; i += 2)dp[0][i] = -prices[0];//2确定递推公式,4确定遍历顺序for (int i = 1; i < prices.size(); i++){for (int j = 0; j < 2*k; j += 2){//第i天第一次持有股票的收入=max(股票不卖(上一天第一次持有股票的收入),第一次买完今天的股票的收入)if(j == 0)dp[i][j] = max(dp[i-1][j], -prices[i]);//第i天第j次持有股票的收入=max(股票不卖(上一天第j次持有股票的收入),第j次买完今天的股票的收入)elsedp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i]);//第i天第j次未持有股票的收入=max(上一天第j次未持有股票的收入,今天第j次卖股票的收入)dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]+prices[i]);}}//输出答案为最后一天第k次未持有股票的结果return dp[prices.size()-1][2*k-1];
}
这篇关于LeetCode 123买卖股票的最佳时机-iii 188买卖股票的最佳时机-iv | 代码随想录25期训练营day50的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!