1. 121. Best Time to Buy and Sell Stock
   1. State Transition Equation
      1. Representing
      2. Boundary Conditions
   2. Code
2. 122. Best Time to Buy and Sell Stock II
   1. State Transition Equation
   2. Code
3. 714. Best Time to Buy and Sell Stock with Transaction Fee
   1. State Transition Equation
   2. Code
4. 309. Best Time to Buy and Sell Stock with Cooldown
   1. State Transition Equation
   2. Code
5. 123. Best Time to Buy and Sell Stock III
   1. Approach
   2. Code
6. 188. Best Time to Buy and Sell Stock IV
7. General Solution for Stock Problems
   1. State Transition Equation
      1. Boundary Conditions
8. Conclusion

121. Best Time to Buy and Sell Stock

State Transition Equation

We can use to represent the maximum profit we can get before day . So, on day , we have two choices:

1. Selling on day  might yield a higher profit compared to the previous profit ().
2. The previous profit is higher, so we don't do anything.

For case 1, the state transition equation is . For case 2, it’s . Combining both cases, we get the state transition equation for this problem:

The challenge now is how to represent .

Representing

We realize that calculating is also a problem of optimal substructure. We can solve it using dynamic programming too. Let represent the lowest price of the stock for the first days. The state transition equation for can be written as:

=

Now, let’s use to represent the maximum profit when we have stocks on day . With this, we can formulate the state transition equation for :

Boundary Conditions

represents the maximum profit when we have 0 stocks on day 0, so .

represents the maximum profit when we have 1 stock on day 0, so .

Code

int maxProfit(vector<int>& prices) {
     const int MAX = 100100;
     int dp[MAX][2];
     dp[0][1] = -prices[0],dp[0][0] = 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(-prices[i], dp[i - 1][1]);
     return dp[prices.size()-1][0];
}

Due to space limitations, optimizing space complexity is left for the reader to contemplate.

122. Best Time to Buy and Sell Stock II

State Transition Equation

The difference between this and problem 121 lies in the fact that multiple buying operations are allowed here. Consequently, the state transition equation changes accordingly.

Based on the state transition equation from problem 121, when we sell on day , our profit can keep accumulating because there’s no restriction on the number of buying operations. Thus, if our maximum profit before day was , after selling on day , it becomes . Hence, the state transition equation for becomes:

Code

int maxProfit(vector<int>& prices) {
     const int MAX = 100100;
     int dp[MAX][2];
     dp[0][1] = -prices[0],dp[0][0] = 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][0]-prices[i], dp[i - 1][1]);
     return dp[prices.size()-1][0];
}

714. Best Time to Buy and Sell Stock with Transaction Fee

State Transition Equation

This problem introduces a fixed transaction fee when selling. If the profit from selling on day isn’t enough to cover the fee, we would prefer the previous profit. Hence, the state transition equation for this problem becomes:

Code

int maxProfit(vector<int>& prices, int fee) {
     const int MAX = 100100;
     int dp[MAX][2];
     dp[0][1] = -prices[0],dp[0][0] = 0;
     for (int i = 1; i < prices.size(); i++)
         dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee),
         dp[i][1] = max(dp[i - 1][0]-prices[i], dp[i - 1][1]);
     return dp[prices.size()-1][0];
}

309. Best Time to Buy and Sell Stock with Cooldown

State Transition Equation

This problem introduces a cooldown period after selling, meaning we can’t buy on the next day after selling. This changes the buying state transition equation as it can only happen after a cooldown period. Thus, the state transition equations become:

Code

int maxProfit(vector<int>& prices) {
     const int MAX = 100100;
     int dp[MAX][3];
     dp[0][1] = -prices[0],dp[0][0] = 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][2]-prices[i], dp[i - 1][1]), //
         dp[i][2] = dp[i - 1][0];
     return dp[prices.size()-1][0];
}

123. Best Time to Buy and Sell Stock III

Approach

This problem extends the concept from problem 121 and 122 by introducing a limit on the number of transactions (). We use a three-dimensional array to represent the maximum profit with two transactions allowed.

Code

int maxProfit(vector<int>& prices) {
    const int MAX = 100100;
    int dp[MAX][2][2];
    dp[0][1][1] = dp[0][1][0] = -prices[0];
    for (int i = 1; i < prices.size(); i++){
        dp[i][0][0] = max(dp[i - 1][0][0], dp[i - 1][1][0] + prices[i]),
        dp[i][1][0] = max(-prices[i], dp[i - 1][1][0]);
        dp[i][0][1] = max(dp[i - 1][0][1], dp[i - 1][1][1] + prices[i]),
        dp[i][1][1] = max(dp[i - 1][0][0]-prices[i], dp[i - 1][1][1]);
    }
    return dp[prices.size()-1][0][1];
}

Although not elegant, this code effectively solves the problem.

188. Best Time to Buy and Sell Stock IV

When the problem extends to , the approach used in problem 123 remains effective. We initialize the boundary as 0 and then use a for loop to calculate the result.

 int maxProfit(int k, vector<int>& prices) {
    if(prices.empty()) return NULL;
    const int MAX = 1100;
    int dp[MAX][2][110]={0};
    for(int j = 0; j <= k; j++) dp[0][1][j] = -prices[0];
    for(int i = 1; i < prices.size(); i++)
        for(int  j = 1; j <= k ; j++)
            dp[i][0][j] = max(dp[i-1][1][j] + prices[i], dp[i-1][0][j]),
            dp[i][1][j] = max(dp[i-1][0][j-1] - prices[i], dp[i-1][1][j]);
    return dp[prices.size()-1][0][k];
 }

General Solution for Stock Problems

State Transition Equation

For stock problems, the three limiting factors are:

• Current day
• Stocks held
• Maximum operations allowed

Let represent the maximum profit on day with stocks and operations allowed. The state transition equation becomes:

Boundary Conditions

All other values are 0.

Conclusion

Stock problems have a close relationship with the concept of dynamic programming. Understanding the different types of dynamic programming problems can significantly help in quickly identifying subproblems and formulating state transition equations.