dede分类信息网站,莆田网站建设公司,做代金券的网站,浅谈你对大学校园网站建设的建议想死#xff0c;但感觉死的另有其人#xff0c;#xff0c;怎么还在动态规划#xff01;#xff01;#xff01;#xff01;#xff01; 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 第一题#xff1a;买卖股票的最佳时机III 给定一个数组#xff0c;它…想死但感觉死的另有其人怎么还在动态规划 123.买卖股票的最佳时机III 188.买卖股票的最佳时机IV 第一题买卖股票的最佳时机III 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1: 输入prices [3,3,5,0,0,3,1,4] 输出6 解释在第 4 天股票价格 0的时候买入在第 6 天股票价格 3的时候卖出这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3。 就是说对于这个股票只能进行最多四次操作买了卖了然后再买再卖 动规五部曲 1确定dp数组以及下标的含义 一天可以发生5种情况 0. 没有操作 1.第一次持有股票 2.第一次不持有股票 3.第二次持有股票 4.第二次不持有股票 这里还是使用二维数组但是之前只有dp[i][0]和dp[i][1]两种情况这里dp[i][j]中表示第i天j为[0-4]共5个状态dp[i][j]表示第i天状态j所剩最大现金。 2确定递推公式 达到dp[i][1]状态有两个具体的操作 操作一第i天买入股票那么dp[i][1]dp[i-1][0]-prices[i] 操作二第i天没有操作dp[i][1]dp[i-1][1] dp[i][1]max(dp[i-1][0]-prices[i], dp[i-1][1])还是取最大的情况 dp[i][2]也有两种具体操作 操作一第i天卖出了股票那么dp[i][2]dp[i-1][1]prices[i] 操作二第i天没有卖出股票跟前一天一样dp[i][2]dp[i-1][2] 同理dp[i][2]max(dp[i-1][1]prices[i], dp[i-1][2]); 同上 dp[i][3]和dp[i][4]一样的计算方法 3dp数组如何初始化 第0天没有操作即dp[0][0]0 第0天做第一次买入的操作即dp[0][1]-prices[0] 第0天做第一次卖出的操作因为没有股票所以没有卖出的东西dp[0][2]0 同理第二次买进卖出: dp[0][3]-prices[0]; dp[0][4]0 4确定遍历顺序 从前向后遍历 5举例推导dp数组 似乎有一些理解了之前只能买进卖出各一次所以对于i天来说可以买进或者卖出dp[i][0]就是买进操作dp[i][1]就是卖出操作最后求出最大的值 第二题买卖股票的最佳时机IV 给定一个整数数组 prices 它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 示例 1 输入k 2, prices [2,4,1] 输出2 解释在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2。 相比上一题k成了可变的 也就是进行k此买进k次卖出 其他规则和上题一样 只要dp[i][j]的下标有了新的意义int j0;j2*k-1;j 为什么呢因为k次交易就一共是2k次动作每一次都可以买卖或者不操作 //首先dp[0][0]不做操作为0//然后dp[0][1]表示第一次买进//dp[0][3]表示第二次买进前面可能都没有操作所以“第一次”买进的时候钱为-prices[0];for(int j1;j2*k;j2){ dp[0][j]-prices[0];}
