Why below recursive DP solution is so slow? (Leetcode Q# 123 - Best Time to Buy and Sell Stock III)

Question

This is regarding leetcode Question# 123. I have solved the question (code below) but the solution is showing "Your runtime beats 5.89 % of cpp submissions."? Is there any additional optimization I can do to make it run faster?

class Solution {
    int maxProfitUtility(vector<int>& prices, int i, int buyOrSell, int k, vector<vector<vector<int>>>& dp){
        if(i == prices.size() || k == 0){
            return 0;
        }
        if(dp[i][buyOrSell][k] != INT_MIN){
            return dp[i][buyOrSell][k];
        }
        int x, y;
        if(buyOrSell == 0){
            x = maxProfitUtility(prices, i + 1, 1, k - 1, dp) - prices[i];
            y = maxProfitUtility(prices, i + 1, 0, k, dp);
        }else{
            x = maxProfitUtility(prices, i + 1, 0, k - 1, dp) + prices[i];
            y = maxProfitUtility(prices, i + 1, 1, k, dp);
        }
        dp[i][buyOrSell][k] = max(x,y);
        return max(x,y);
    }
public:
    int maxProfit(vector<int>& prices) {
        int k = 4;
        vector<vector<vector<int>>> dp(prices.size(), vector<vector<int>>(2, vector<int>(k + 1, INT_MIN)));
        return maxProfitUtility(prices, 0, 0, k, dp);
    }
};

Answer 1

Recursion comes with overheads. You need to push to the call stack and create a new context for your code to execute in.

I would convert this to an iterative solution.

You also don't need to allocate so much memory. Think closely about what information you actually need. HINT: If you could only go long on the stock, you would only need to store 2 ints as you iterate over the list to get your maximum profit.

Furthermore leetcode has the option of viewing code from the fastest solutions. Check that out and if you don't understand why their solution is so much faster, post on stack overflow.