> Solutions for tree coins in a line problem

This is a post for game theory problems. All solutions are written in Python.

I didn’t have to put a lot of details here. Comment below if you have any issue.

Keep in mind: the current state is generated by its sub states (further states).

> Coins in a line I

  • Problem: http://www.lintcode.com/en/problem/coins-in-a-line/

    This problem start taking coins from the right side.

  • Solution:

    1. DP
    class Solution:
    """
    @param n: an integer
    @return: a boolean which equals to True if the first player will win
    """
    def firstWillWin(self, n):
    dp = [False] * (n+1)

    for i in range(1, n+1):
    if not (dp[i-1] and dp[i-2]):
    dp[i] = True
    return dp[n]

dp[i] represents if the current player can win when i~n coins have been selected.

For not (dp[i-1] and dp[i-2]), dp[i] is True when and only when there is a False in dp[i]'s sub states dp[i-1] and dp[i-2]. Which means, there is a possible lose for his opponent. dp[i]'s sub states represent the coins his opponent can gain. We want this value smaller so that we can gain more.

  1. Search
class Solution:
def firstWillWin(self, n):
def search(i, dp, visited):
if visited[i]:
return dp[i]
if i == 0:
dp[i] = False
elif i == 1:
dp[i] = True
elif i == 2:
dp[i] = True
else:
dp[i] = not (search(i-1, dp, visited) and search(i-2, dp, visited))

visited[i] = True
return dp[i]

dp = [False] * (n+1)
visited = [False] * (n+1)
return search(n, dp, visited)

> Coins in a line II

  • Problem: http://www.lintcode.com/en/problem/coins-in-a-line-ii/

    This problem starts taking coins from the left side.

  • Solution:

    1. DP
    class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """
    def firstWillWin(self, values):
    n = len(values)
    if n <= 2:
    return True
    dp = [0] * (n + 1)
    dp[n] = 0; dp[n-1] = values[n-1]; dp[n-2] = values[n-1] + values[n-2]

    sum = [0] * (n + 1)
    for i in range(n-1, -1, -1):
    sum[i] = sum[i+1] + values[i]

    for i in range(n-3, -1, -1):
    dp[i] = sum[i] - min(dp[i+1], dp[i+2])
    return dp[0] > sum[0] / 2

    dp[i] means the max coins can gain from i to end

    sum[i] means the sum from i to end

    dp[i] = max(values[i] + sum[i+1] - dp[i+1], values[i] + values[i+1] + sum[i+2] - dp[i+2]) => dp[i] = sum[i] - min(dp[i+1], dp[i+2])

    1. Search
    class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """

    def firstWillWin(self, values):
    def search(i, dp, visited):
    if visited[i]:
    return dp[i]
    if i == n:
    dp[i] = 0
    elif i == n - 1:
    dp[i] = values[n - 1]
    elif i == n - 2:
    dp[i] = values[n - 1] + values[n - 2]
    else:
    dp[i] = self.sum[i] - min(search(i + 1, dp, visited), search(i + 2, dp, visited))

    visited[i] = True
    return dp[i]

    n = len(values)
    dp = [0] * (n + 1)
    visited = [False] * (n + 1)
    self.sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
    self.sum[i] = self.sum[i + 1] + values[i]
    return search(0, dp, visited) > self.sum[0] / 2

> Coins in a line III

  • Problem:

    There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

    Could you please decide the first player will win or lose?

  • Example

    Given array A = [3,2,2], return true.

    Given array A = [1,2,4], return true.

    Given array A = [1,20,4], return false.

  • Solution:

    1. DP
    class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """
    def firstWillWin(self, values):
    n = len(values)
    dp = [[0] * (n+1) for _ in range(n+1)]

    ''' sum for array [i, j), i includes, j excludes '''
    sum = [0]
    for i in range(n):
    sum.append(sum[-1] + values[i])

    for i in range(n, -1, -1):
    for j in range(i+1, n+1):
    ''' initialization '''
    if i+1 == j:
    dp[i][j] = values[i]
    else:
    dp[i][j] = sum[j] - sum[i] - min(dp[i+1][j], dp[i][j-1])

    return dp[0][n] > sum[n] / 2

    dp[i][j]=max(values[i]+sum[i+1][j]-dp[i+1][j], values[j]+sum[i][j-1]-dp[i][j-1])

    values[i]+sum[i+1][j] and values[j]+sum[i][j-1] are equal to sum[i][j]

    So dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])

    1. Search
    class Solution:
    """
    @param: values: a vector of integers
    @return: a boolean which equals to true if the first player will win
    """

    def firstWillWin(self, values):
    def search(start, end, sum, dp, visited):
    if visited[start][end]:
    return dp[start][end]
    elif start == end:
    dp[start][end] = sum[end] - sum[start-1]
    else:
    dp[start][end] = sum[end] - sum[start-1]\
    - min(search(start+1, end, sum, dp, visited), search(start, end-1, sum, dp, visited))

    visited[start][end] = True
    return dp[start][end]

    if not values:
    return False
    n = len(values)

    sum = [0] * (n+1)
    ''' sum for array [i, j], i includes, j includes '''
    for i in range(1, n+1):
    sum[i] = sum[i-1] + values[i-1]

    dp = [[0] * (n+1) for _ in range(n+1)]
    visited = [[False] * (n+1) for _ in range(n+1)]

    return search(1, n, sum, dp, visited) > sum[n] / 2