brute force and memoization


  • 7
    1. O(n!) brute force, n is maxChoosableInteger. T(n)=nT(n-1)
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(!desiredTotal) return 1;
            return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal);
        }
        bool canWin(int pool, int maxint, int tot) {
            if(tot<=0) return 0;
            for(int i=0;i<maxint;i++) {
                int mask = 1<<i;
                if(pool & mask) continue;
                pool|=mask;
                if(!canWin(pool,maxint, tot-i-1)) return 1;
                pool^=mask;
            }
            return 0;
        }
    
    1. O(2^n) Memoization. There is redundant computation in #1. A state with a pool and total may be computed many times. So we can cache the state and reuse it. At first glance, it seems that a state is determined by two values, the pool and the total. However, since the initial total is known, the remaining total is known given the pool. So a state can be identified by the pool only.
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(!desiredTotal) return 1;
            if(maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal) return 0;
            unordered_map<int,char> mem;
            return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal, mem);
        }
        bool canWin(int pool, int maxint, int tot, unordered_map<int,char>& mem) {
            if(tot<=0) return 0;
            auto it = mem.find(pool);
            if(it != mem.end()) return it->second;
            for(int i=0;i<maxint;i++) {
                int mask = 1<<i;
                if(pool & mask) continue;
                pool|=mask;
                if(!canWin(pool,maxint,tot-i-1,mem)) return mem[pool^=mask]=1;
                pool^=mask;
            }
            return mem[pool] = 0;
        }
    
    1. Iterative dp. For most dp problems, the next step is to transform recursion with memoization to iterative dp. However, that does not help and is actually pretty bad for this problem. In iterative dp, we have to visit all the 2^n states to get the result. In #2 DFS with memoization, DFS terminates as soon as it finds a way to win. The worst case O(2^n) rarely happens. So if DFS has early termination condition, then it should be better than dp that visits all the states. Similar problems are word break and Concatenated Words.

  • 0
    P

    @yu6
    Could please explain the condition if(tot<=0) return 0; in canWin function.
    if tot == 0 return 0; seems fine. But if tot<0 why the function is returning "0".


  • 1

    @pradeepkv09
    According to the problem description, the player who first causes the running total to reach or exceed the desiredTotal wins. If a player sees negative total in his turn, it means the other player causes the running total to exceed the desiredTotal in the previous move and wins.


  • 0
    D

    Thank you for sharing. I simplified a little bit.

    class Solution {
        bool canWin(int pool, int maxint, int tot, unordered_map<int, bool>& memo) {
            if(tot <= 0) return false;
            auto it = memo.find(pool);
            if (it != memo.end()) return it->second;
            for(int i = 1; i <= maxint; i++) {
                int mask = 1<<i;
                if(pool & mask) continue;
                if(!canWin(pool | mask, maxint, tot-i, memo)) {
                    return memo[pool] = true;
                }
            }
            return memo[pool] = false;
        }    
    public:
        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(desiredTotal == 0) return true;
            if(maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal) return false;        
            unordered_map<int, bool> memo;
            return canWin(0, maxChoosableInteger, desiredTotal, memo);
        }
    

  • 0
    R
    This post is deleted!

  • 0
    S

    @yu6
    From a pool of numbers as we have 2 players they need to select numbers taking turns ,so i added a playerflag .
    if playerflag is true that means it is is player1 turn and we are looking for his win.
    In the code I check if desiredTotal reaches 0 and playerflag== true.
    Why does this code not work,What did I misunderstand?

    #include <vector>
    #include <iostream>
    #include <unordered_map>
    #include <algorithm>
    
    using namespace std;
    
    bool canWin(int pool, int maxint, int tot, bool flag);
    
    bool canIWin(int maxChoosableInteger, int desiredTotal) 
    {
            if(!desiredTotal) return 1;
            return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal, false);
    }
    
    
    bool canWin(int pool, int maxint, int tot, bool playerflag) 
    {
    		
    
            if(tot<=0 && playerflag == false)
            { 
            	return false;
            }
            else if(tot <= 0 && playerflag == true)
            {
            	
            	return true;
            }
    
            (playerflag)?playerflag = false:playerflag = true;
    
            for(int i=0;i<maxint;i++) 
            {
                int mask = 1<<i;
    
                if(pool & mask) continue;
    
                pool|=mask;
    
                bool flag = canWin(pool,maxint, tot-i-1, playerflag);
                if(flag)
                {
                	return true;
                }
                pool^=mask;
            }
            
            return false;
    }
    

  • 0

    @skocharl My solution does not need the player flag, canWin just means if a player can win given the pool and total. Adding the player flag makes it more complicated. canWin() becomes if player 1 can win given the pool, total can starting player.

        bool canIWin(int maxChoosableInteger, int desiredTotal) {
            if(!desiredTotal) return 1;
            return canWin(~0<<maxChoosableInteger, maxChoosableInteger, desiredTotal,1);
        }
        bool canWin(int pool, int maxint, int tot, bool player) {
            if(tot<=0) return !player;
            for(int i=0;i<maxint;i++) {
                int mask = 1<<i;
                if(pool & mask) continue;
                pool|=mask;
                bool canP1win = canWin(pool,maxint, tot-i-1,!player);
                if(player && canP1win) return 1;
                if(!player && !canP1win) return 0;
                pool^=mask;
            }
            return !player;
        }
    

Log in to reply
 

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