网站活动怎么做,温州网络投诉平台,网站便宜建设,网站建设 教学视频买卖股票的最佳时机I
121. 买卖股票的最佳时机 - 力扣#xff08;LeetCode#xff09;
之前用贪心算法做过相同的题#xff0c;这次考虑使用动态规划来完成。
dp[i]表示前i天的最大利润
我们已知每一天的价格price[i]#xff0c;则dp[i]为每一天的价格price[i]减去当初…买卖股票的最佳时机I
121. 买卖股票的最佳时机 - 力扣LeetCode
之前用贪心算法做过相同的题这次考虑使用动态规划来完成。
dp[i]表示前i天的最大利润
我们已知每一天的价格price[i]则dp[i]为每一天的价格price[i]减去当初购买的价格buyprice与dp1[i-1]的较大值。 dp[i] max(dp[i-1],price[i]-buyprice)。
dp[0]表示收益为0
从前往后递推注意要更新buyprice的价格为当前遍历过的数据中最小的值。
最后返回dp[price.size()-1]。
其实和贪心差不多或者说贪心是这里动态规划的变体
class Solution {
public:int maxProfit(vectorint prices) {// 如果价格数组为空则没有利润返回0if(prices.size()0)return 0;// 初始化买入价格为第一天的价格int buyprice prices[0];// 创建一个动态数组dp用于存储到第i天为止的最大利润// 初始化dp[0]为0因为第一天买入卖出没有利润vectorintdp(prices.size(),0);dp[0] 0;// 遍历价格数组从第二天开始for(int i 1;i prices.size();i){// 更新买入价格为当前价格和之前最低价格中的较小值buyprice min(buyprice,prices[i]);// 计算如果在今天卖出股票能获得的最大利润// 即取当前价格减去最低买入价格和前一天的最大利润中的较大值dp[i] max(dp[i-1],prices[i]-buyprice);}// 返回最后一天的最大利润即整个期间的最大利润return dp[prices.size()-1];}
};算法的时间复杂度为O(n)遍历一次数组空间复杂度同样为O(n)需要维护一个dp数组。
买卖股票的最佳时机II
122. 买卖股票的最佳时机 II - 力扣LeetCode
由于不能同时参与多笔交易则每天结束只会存在拥有一支股票和无股票两种情况由次创建一个二维的dp数组n*2的大小其中dp[i][0]表示当天结束时手头没有股票的最大利润dp[i][1]表示当天结束时手头有股票的利润。
考虑推导手头没有股票有两种情况一是前一天就没有股票且今天没买二是前一天有股票但今天卖了则dp[i][0] max(dp[i-1][0],dp[i-1][1]price[i])手头有股票同样有两种情况一是前一天没有股票但今天买了二是昨天的股票没卖。
dp[i][1] max(dp[i-1][0] - price[i],dp[i-1][1])
考虑到这样的情况需对dp[0][0]和dp[1][0]初始化dp[0][0] 0,dp[0][1]-price[0]
从前往后遍历本质上还是从天来推导
最后一天由于dp[i][0]一定大于dp[i][1]返回dp[i][0]即可。
class Solution {
public:int maxProfit(vectorint prices) {// 创建一个二维数组dp行数为prices的大小列数为2// dp[i][0]代表第i天结束时不持有股票的最大利润// dp[i][1]代表第i天结束时持有股票的最大利润vectorvectorint dp(prices.size(), vectorint(2, 0));// 初始化dp数组的第一行// 第一天不持有股票的最大利润为0dp[0][0] 0; // 第一天持有股票的最大利润为负的第一天价格即买入股票dp[0][1] -prices[0];// 遍历价格数组从第二天开始更新dp数组for(int i 1; i prices.size(); i){// 更新第i天不持有股票的最大利润// 可以是前一天就不持有股票或者前一天持有股票但今天卖出dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]);// 更新第i天持有股票的最大利润// 可以是前一天就持有股票或者前一天不持有股票但今天买入dp[i][1] max(dp[i-1][0] - prices[i], dp[i-1][1]);}// 返回最后一天不持有股票的最大利润return dp[prices.size()-1][0];}
};
算法的时间复杂度为O(n)空间复杂度为O(n)。
买卖股票的最佳时机III
123. 买卖股票的最佳时机 III - 力扣LeetCode
每天结束后我们手中持有的股票有以下五种情况。
无操作第一次买操作完成一笔操作第二次买操作完全两笔交易
由此我们根据买卖股票的最佳时机II相似的方式来完成本题。 dp[i][0]没有进行任何交易时的利润。 dp[i][1]进行了第一次买入后的利润。 dp[i][2]完成了第一次卖出后的利润。 dp[i][3]进行了第二次买入后的利润。 dp[i][4]完成了第二次卖出后的利润。
dp[i][0]始终为0这里我们将dp[i][0] do[i-1][0];
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])
dp[i][4] max(dp[i-1][4],dp[i-1][3] prices[i])
从前向后遍历
返回dp[prices.size()-1][4]
class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0; // 如果没有价格数据则利润为0vectorvectorint dp(prices.size(), vectorint(5, 0)); // 初始化dp数组// 初始化第一天的状态dp[0][1] -prices[0]; // 第一天买入股票后的利润dp[0][3] -prices[0]; // 假设k2第一天买入第二次股票后的利润for (int i 1; i prices.size(); i) { // 遍历价格数组// 更新第i天不进行任何交易的最大利润这个值始终为0因为不交易不会有利润变化dp[i][0] dp[i - 1][0];// 更新第i天进行第一次买入后的最大利润dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);// 更新第i天完成第一次卖出后的最大利润dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);// 更新第i天进行第二次买入后的最大利润dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);// 更新第i天完成第二次卖出后的最大利润dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);}// 返回最后一天完成所有交易后的最大利润return dp[prices.size() - 1][4];}
};算法的时间复杂度为O(n)空间复杂度为O(n)。
