This is the link for a problem I am trying to solve:
188. Best Time to Buy and Sell Stock IV
I have come up with an approach, but cannot figure out why this approach is not working, even on the 2nd sample test case.
This is my implementation:
<code>class Solution {
public:
int MN = (2e7)*(-1);
int f(vector<vector<int>> &dp, vector<vector<bool>> &vis, int i, int k, bool buy, bool sell, bool no, vector<int> &prices) {
if(k < 0) {
return MN;
}
if(i == prices.size()) {
return 0;
}
if(vis[i][k]) {
return dp[i][k];
}
if(buy) { // if buying is allowed, we buy and then set the buy variable false and make sell true.
dp[i][k] = max(dp[i][k], (prices[i]*(-1) + f(dp, vis, i+1, k-1, false, true, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices)); // This condition is for the cases when I am not buying or selling that day.
}
if(sell) {
dp[i][k] = max(dp[i][k], (prices[i] + f(dp, vis, i+1, k, true, false, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices));
}
vis[i][k] = true;
return dp[i][k];
}
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(k+1, MN));
vector<vector<bool>> vis(n, vector<bool>(k+1)); // used for memoization
int m = f(dp, vis, 0, k, true, false, true, prices);
return m;
}
};
</code>
<code>class Solution {
public:
int MN = (2e7)*(-1);
int f(vector<vector<int>> &dp, vector<vector<bool>> &vis, int i, int k, bool buy, bool sell, bool no, vector<int> &prices) {
if(k < 0) {
return MN;
}
if(i == prices.size()) {
return 0;
}
if(vis[i][k]) {
return dp[i][k];
}
if(buy) { // if buying is allowed, we buy and then set the buy variable false and make sell true.
dp[i][k] = max(dp[i][k], (prices[i]*(-1) + f(dp, vis, i+1, k-1, false, true, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices)); // This condition is for the cases when I am not buying or selling that day.
}
if(sell) {
dp[i][k] = max(dp[i][k], (prices[i] + f(dp, vis, i+1, k, true, false, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices));
}
vis[i][k] = true;
return dp[i][k];
}
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(k+1, MN));
vector<vector<bool>> vis(n, vector<bool>(k+1)); // used for memoization
int m = f(dp, vis, 0, k, true, false, true, prices);
return m;
}
};
</code>
class Solution {
public:
int MN = (2e7)*(-1);
int f(vector<vector<int>> &dp, vector<vector<bool>> &vis, int i, int k, bool buy, bool sell, bool no, vector<int> &prices) {
if(k < 0) {
return MN;
}
if(i == prices.size()) {
return 0;
}
if(vis[i][k]) {
return dp[i][k];
}
if(buy) { // if buying is allowed, we buy and then set the buy variable false and make sell true.
dp[i][k] = max(dp[i][k], (prices[i]*(-1) + f(dp, vis, i+1, k-1, false, true, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices)); // This condition is for the cases when I am not buying or selling that day.
}
if(sell) {
dp[i][k] = max(dp[i][k], (prices[i] + f(dp, vis, i+1, k, true, false, no, prices)));
dp[i][k] = max(dp[i][k], f(dp, vis, i+1, k, buy, sell, no, prices));
}
vis[i][k] = true;
return dp[i][k];
}
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(k+1, MN));
vector<vector<bool>> vis(n, vector<bool>(k+1)); // used for memoization
int m = f(dp, vis, 0, k, true, false, true, prices);
return m;
}
};
Also, could someone suggest any methods to debug this issue? With this much recursion, it’s hard to keep track and understand.
2