Calculate the winning strategy of a subtraction game


  • 0
    Y

    Problem:
    Given 100 stones, two players alternate to take stones out. One can take any number from 1 to 15; however, one cannot take any number that was already taken. If in the end of the game, there is k stones left, but 1 - k have all been previously taken, one can take k stones. The one who takes the last stone wins. How can the first player always win?

    My Idea
    Use recursion (or dynamic programming). Base case 1, where player 1 has a winning strategy.
    Reducing: for n stones left, if palyer 1 takes m1 stones, he has to ensure that for all options player 2 has (m2), he has a winning strategy. Thus the problem is reduced to (n - m1 - m2).

    Follow Up Question:
    If one uses DP, the potential number of tables to be filled is large (2^15), since the available options left depend on the history, which has 2^15 possibilities.
    How can you optimize?

    I don't have a great answer to the follow up question。。。


Log in to reply
 

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