首页 > 编程学习 > 随想录一刷Day49——动态规划

随想录一刷Day49——动态规划

发布时间:2022/11/9 2:36:56

文章目录

  • Day49_动态规划
    • 32. 买卖股票的最佳时机
    • 33. 买卖股票的最佳时机 II

Day49_动态规划

32. 买卖股票的最佳时机

121. 买卖股票的最佳时机
思路一:

由于股票最多买入卖出一次,所以记录前面出现的最低股票价格,找到最低价格之后的最高价格出售,这里要注意统计的顺序,不要还没有买入就卖出了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prices_size = prices.size();
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices_size; i++) {
            low = min(low, prices[i]);
            result = max(result, prices[i] - low);
        }
        return result;
    }
};

思路二:

dp

  1. dp[i][0]代表第i天手上不持股的最大持有现金数,
    dp[i][1]代表第i天手上持股的最大持有现金数
  2. 递推公式:
  • dp[i][0] = max(dp[i-1][0], dp[i-1][0] + prices[i]); // max(前一天不持股,前一天持股但今天卖出去了)
  • dp[i][1] = max(-prices[i], dp[i-1][1]); // max(前一天不持股今天买入,前一天持股今天不卖出)
  1. 初始化:第一天买入或者不买入
  • dp[0][1] = -prices[0]
  • dp[0][0] = 0
  1. 递推顺序,每个dp[i-1]由其前一天递推而来,所以递归顺序从前往后
  2. 样例推演,偷图(不过图中的0和1与我的定义相反)
    在这里插入图片描述
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prices_size = prices.size();
        if (prices_size == 0) return 0;
        vector<vector<int>> dp(prices_size, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices_size; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }
        return dp[prices_size - 1][0]; // 一定是不持股的现金多,持股手上现金数为负
    }
};

33. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II
思路

dp

  1. dp[i][0]表示第i天不持股的现金数
    dp[i][1]表示第i天持股的现金数
  2. 递推公式
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) // 前一天不持股今保持,前一天持股今日卖出
  • dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]) // 前一天不持股今日买入,前一天持股今日保持
  1. 初始化:
  • dp[0][0] = 0
  • dp[0][1] = -prices[i]
  1. 递推顺序,从前往后

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prices_size = prices.size();
        if (prices_size == 0) return 0;
        vector<vector<int>> dp(prices_size, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices_size; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices_size - 1][0];
    }
};

利用滚动数组优化空间:
由于每天只用到了前一天的值,所以数组空间只需要开今天和昨天两天的维度大小即可

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prices_size = prices.size();
        if (prices_size == 0) return 0;
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < prices_size; i++) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] + prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] - prices[i]);
        }
        return dp[(prices_size - 1) % 2][0];
    }
};
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式