what is wrong with DFS+ memorization?


  • 0
    J
    class Solution {
    public:
        enum action {FLAT,BUY,SELL};
        int maxProfit(vector<int>& prices) {
            
            vector<vector<int>> states(prices.size(),vector<int>(3,-1));
            return dfs(0,states,prices,FLAT);
        }
        int dfs(int idx, vector<vector<int>> states,vector<int>& prices,action _action)
        {
            if(idx>=prices.size()) return 0;
            if(states[idx][_action]!=-1) return states[idx][_action];
            int ans = 0;
            if(_action == FLAT)
                ans = max(dfs(idx+1,states,prices,BUY),dfs(idx+1,states,prices,FLAT));
            else if(_action == SELL)
            {
                
                ans = max(dfs(idx+2,states,prices,BUY),dfs(idx+1,states,prices,FLAT))+prices[idx];
            }
            else
                ans = dfs(idx+1,states,prices,FLAT);
            
            states[idx][_action] = ans;
            return ans;
        }
    };
    

  • 0
    J

    When are you selling? in all your actions you pass either BUY or FLAT, you never pass SELL so you'll never
    get to the code where you actually SELL

    Not that used to c++ anymore so take it with a grain of salt, but I think that's where the mistake lies.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.