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);
}
};