代码随想录算法训练营第四十天|Day40 动态规划

121. 买卖股票的最佳时机

视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q

https://programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
int maxProfit(int* prices, int pricesSize) {int low = INT_MIN;int result = 0;for(int i = 0; i < pricesSize; i++){low = min(low, prices[i]);result = max(result, prices[i] - low);}return result;
}

学习反思

通过定义宏max和min来实现获取两个数中的最大值和最小值。宏的使用可以简化代码，提高可读性。然后，在函数内部定义了两个变量low和result，分别用来存储最低价格和最大收益。接下来，通过循环遍历prices数组，更新low和result的值。首先使用宏min来更新low，将当前价格和low比较取较小值。然后使用宏max来更新result，将当前价格减去low的差值与当前result比较取较大值。最后，返回result作为最大收益。

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

视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
int maxProfit(int* prices, int pricesSize){int **dp = malloc(sizeof (int *) * pricesSize);for (int i = 0; i < pricesSize; ++i) {dp[i] = malloc(sizeof (int ) * 2);}dp[0][0] = -prices[0];dp[0][1] = 0;for (int i = 1; i < pricesSize; ++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[pricesSize - 1][1];
}

学习反思

使用了一个二维数组dp来记录每天持有或不持有股票时的最大收益。dp[i][0]表示第i天持有股票时的最大收益，dp[i][1]表示第i天不持有股票时的最大收益。首先，初始化dp数组的第一行，即第0天的情况。dp[0][0]表示第0天持有股票时的最大收益，由于要买入股票，所以收益为-prices[0]。dp[0][1]表示第0天不持有股票时的最大收益，由于没有买入股票，所以收益为0。然后，从第1天开始遍历每一天，更新dp数组。对于第i天持有股票的最大收益，有两种情况：要么是前一天持有股票的最大收益dp[i-1][0]，要么是前一天不持有股票的最大收益减去当天股票价格prices[i]。取其中的较大值更新dp[i][0]。对于第i天不持有股票的最大收益，也有两种情况：要么是前一天不持有股票的最大收益dp[i-1][1]，要么是前一天持有股票的最大收益加上当天股票价格prices[i]。取其中的较大值更新dp[i][1]。最后，返回dp数组的最后一行的第一个元素dp[pricesSize-1][1]，即最后一天不持有股票的最大收益，也就是问题要求的最大收益。这段代码的时间复杂度为O(n)。

123.买卖股票的最佳时机III

视频讲解：https://www.bilibili.com/video/BV1WG411K7AR

https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html

思路

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
int maxProfit(int* prices, int pricesSize) {int buy1 = prices[0], buy2 = prices[0];int profit1 = 0, profit2 = 0;for (int i = 0; i < pricesSize; ++i) {buy1 = min(buy1, prices[i]);profit1 = max(profit1, prices[i] - buy1);buy2 = min(buy2, prices[i] - profit1);profit2 = max(profit2, prices[i] - buy2);}return profit2;
}

学习反思

来计算股票的最大利润。代码中定义了两个宏：max和min，用来求两个值的较大值和较小值。然后定义了四个变量：buy1、buy2、profit1和profit2，分别表示第一次购买的价格、第二次购买的价格、第一次交易的利润和第二次交易的利润。接下来使用循环遍历股票价格数组。在每次循环中，分别更新buy1和profit1。buy1取当前价格和buy1的较小值，表示第一次购买的最低价格。profit1取当前价格减去buy1和profit1的较大值，表示第一次交易的最大利润。然后更新buy2和profit2。buy2取当前价格减去profit1和buy2的较小值，表示第二次购买的最低价格。profit2取当前价格减去buy2和profit2的较大值，表示第二次交易的最大利润。最后返回profit2,即为最大利润。该算法的时间复杂度是O(n)。