本文共 2118 字，大约阅读时间需要 7 分钟。

lc343 | 买股票问题

在这里，我们将从暴力递归开始，然后逐步改写为动态规划。

暴力递归思路

我们可以采用递归的方法来解决这个问题。假设我们有一个数组 prices，记录股票的价格。每一天，我们可以选择买入、卖出或者不买入股票。递归函数 dfs 可以接受当前的索引 index 和一个布尔 flag，表示是否已经买入股票。

递归函数的逻辑如下：

为了优化递归，我们需要使用记忆化来缓存已经计算过的状态。

动态规划思路

既然我们已经写出了递归函数，我们可以将递归的状态转换为动态规划的状态转移方程。我们可以使用一个二维数组 dp，其中 dp[i][j] 表示到第 i 个交易日，处于状态 j（j = 0 表示没买，j = 1 表示买）的最大利润。

• 初始化：dp[n][0] = 0，dp[n][1] = -prices[n-1]（这里 n 是数组的长度）。
• 从 n-1 往回推，计算每一天的最大利润：
  • 对于每一天 i：
    • 如果当前状态是没买（j=0），那么最大利润可以是买入后卖出的利润加上后续的最大利润，或者不买入，继续后续的最大利润。
    • 如果当前状态是买入（j=1），那么只能卖出，得到利润，加上后续的最大利润。

代码

递归代码：

#include 
   
    using namespace std;class Solution {    int dfs(const vector
    
     & prices, int index, bool flag) {        if (index >= prices.size()) return 0;        if (flag) {            return 0 - prices[index] + dfs(prices, index + 1, false);        } else {            int buy = 0 - prices[index] + dfs(prices, index + 1, true);            int not_buy = dfs(prices, index + 1, false);            return max(buy, not_buy);        }    }public:    int maxProfit(vector
     
       prices) {        return dfs(prices, 0, true);    }};
     
    
   

动态规划代码：

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

代码说明