郑州整站网站推广工具,提交谷歌网站,谷歌外贸建站多少钱,免费网页游戏网目录 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 123.买卖股票的最佳时机III 题目链接#xff1a;123. 买卖股票的最佳时机 III 仿照买卖股票的最佳时机#xff0c;多设置两个状态用于记录第2次是否持有股票#xff1a; #xff08;1#xff09;dp[ i ][ 0 ] 表… 目录 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 123.买卖股票的最佳时机III 题目链接123. 买卖股票的最佳时机 III 仿照买卖股票的最佳时机多设置两个状态用于记录第2次是否持有股票 1dp[ i ][ 0 ] 表示第一次持有股票 dp[ i ][ 1 ] 表示第一次不持有股票 dp[ i ][ 2 ] 表示第二次持有股票 dp[ i ][ 3 ] 表示第二次不持有股票 2dp[ i ][ 0 ] max( dp[ i - 1 ][ 0 ], -prices[ i ] ); dp[ i ][ 1 ] max( dp[ i - 1 ][ 1 ], dp[ i - 1 ][ 0 ] 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 ] ); 3第二次买入的初始情况取决于第一次买入的初始情况 dp[ 0 ][ 2 ] dp[ 0 ][ 0 ] -prices[ 0 ] 4按日期遍历 通过观察我们不难看出 dp数组前后关系只维持了 i 与 i - 1 的关系所以可以压缩数组到一维 class Solution {
public:int maxProfit(vectorint prices) {vectorint dp(4, 0);dp[2] dp[0] -prices[0];for(int i 1; i prices.size(); i){dp[0] max( dp[0], -prices[i] );dp[1] max( dp[1], dp[0] prices[i] );dp[2] max( dp[2], dp[1] - prices[i] );dp[3] max( dp[3], dp[2] prices[i] );}return dp[3];}
}; 188.买卖股票的最佳时机IV 题目链接188. 买卖股票的最佳时机 IV 在买卖股票的最佳时机 Ⅰ、Ⅲ中我们使用二维的 dp数组其中第二维用于表示当前状态 当只能买卖一次时有两种状态当能买卖两次时有4种状态拓展一下 当能买卖 k 次时可以有 2k 种状态并且每种状态之间的关联都是相通的。 当然也可以压缩数组使得 dp 数组仅表示状态。 为了保持统一特地在所有状态前加入了 0 状态表示不进行操作随后是 1 到 2k 个状态。 class Solution {
public:int maxProfit(int k, vectorint prices) {vectorint dp(2 * k 1, 0);for(int i 1; i 2 * k 1; i 2){dp[i] -prices[0];}for(int i 1; i prices.size(); i){for(int j 1; j 2 * k 1; j){dp[j] max(dp[j], dp[j - 1] - prices[i]);j;dp[j] max(dp[j], dp[j - 1] prices[i]);}}return dp[2 * k];}
};
