建材网站制作,专业的网站建设企业,各网站推广,网页视频提取软件123.买卖股票的最佳时机III 题目链接/文章讲解/视频讲解#xff1a;代码随想录 1.代码展现
//123.买卖股票的最佳时机
int maxProfit(vectorint prices) {if (prices.size() 1) {return 0;}//step1 构建dp数组vectorvectorint dp(prices.size(…123.买卖股票的最佳时机III 题目链接/文章讲解/视频讲解代码随想录 1.代码展现
//123.买卖股票的最佳时机
int maxProfit(vectorint prices) {if (prices.size() 1) {return 0;}//step1 构建dp数组vectorvectorint dp(prices.size(), vectorint(5, 0));//dp[i][0]的含义是//dp[i][1]的含义是第一次持有股票的最大金额数//dp[i][2]的含义是第一次未持有卖掉了股票的最大金额数//dp[i][3]的含义是第二次持有股票的最大金额数//dp[i][4]的含义是第二次未持有卖掉了股票的最大金额数//step2 状态转移方程//dp[i][1] max(dp[i - 1][1], -prices[i])//dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i])//dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i])//dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i])//step3 初始化dp数组dp[0][1] -prices[0];dp[0][3] -prices[0];//step4 开始遍历for (int i 1; i prices.size(); i) {dp[i][1] max(dp[i - 1][1], -prices[i]);dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[prices.size() - 1][4];}
2.本题小节 思考本题与昨天的题目不同点在于可以购买两次因此第i天一共有四种状态第一次持有第一次未持有第二次持有第二次未持有每次都有对应的状态转移公式第一次持有的话两种情况前一天的或者是当天买的第一次未持有要么就是前一天未持有或者是今天卖的是前一天持有的金钱加上卖票的金钱第二次持有的同理。同时注意每一次持有的初始化即-price[0]。 基本思路明确状态转移公式和初始化。
188.买卖股票的最佳时机IV 题目链接/文章讲解/视频讲解代码随想录 1.本题小节
//188 买卖股票的最佳时机
int maxProfit(int k, vectorint prices) {if (prices.size() 1) {return 0;}//step1 构建dp数组vectorvectorint dp(prices.size(), vectorint(2 * k 1, 0));//step2 状态转移方程//step3 初始化for (int j 0; j 2 * k; j 2) {dp[0][j 1] -prices[0];}//step4 开始遍历for (int i 1; i prices.size(); i) {for (int j 0; j 2 * k; j 2){//持有股票dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i]);//未持有股票dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i]);}}return dp[prices.size() - 1][2 * k];
}
2.本题小节 思考本题是可以买卖k次通过上一题可以找到规律主要是明确状态转移公式要对1-k次依次创建状态转移公式每天k次的状态都是持有和不持有两种因此状态转移方程共有2k个但是每次的的两种情况规律是一样的每次持有的状态是两种情况前一天的持有状态或者是前一天未持有的状态减去prices[i]未持有的状态也是两种情况前一天未持有的状态或者是今天卖出股票的状态。注意初始化和上一题一样但是有k次初始化需要for循环遍历。 基本思路明确状态转移公式和初始化。
