Why I'm wrong? Just wana from recursive DFS


  • 0
    Y

    I write a simple recursive DFS, and it pass lots of test cases, but failed on the case (10, 40). My codes are as follows. Why it's wrong?
    '''

    public class Solution {
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        return dfs(1, maxChoosableInteger, desiredTotal);
    }
    
    boolean dfs(int st, int ed, int target){
        if (ed >= target) return true;
        if (st == ed) return false;
        
        for (int i=st; i <=ed; i++){
            if (i==st){
                if (!dfs(i+1, ed, target - i)) 
                    return true;
            }else if (i==ed){
                if (!dfs(st, i-1, target - i))
                    return true;
            }else{
                if (!dfs(st, i-1, target - i) && !dfs(i+1, ed, target - i)) 
                    return true;
            }
        }
        return false;
    }
    

    }

    '''


  • 0
    B
    This post is deleted!

  • 0

    The bug is in the last condition check:

                if (!dfs(st, i-1, target - i) && !dfs(i+1, ed, target - i)) 
                    return true;
    

    If a middle value i is picked by the current player, the problem cannot be reduced to two sub problems as you defend by start and end available numbers in the pool because you won't know what would be the associated desired total to achieve for each sub problem.

    Actually, it's not a good idea to define start, end available numbers in your dfs routine since they can't characterize a state of the game.


Log in to reply
 

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