DP - Game

Algorithms
dfs, dp
Catalogue
  1. 1. DFS + Memorization
    1. 1.1. 464. Can I Win
    2. 1.2. 293. Flip Game
    3. 1.3. 294. Flip Game II
  2. 2. DP
    1. 2.1. LintCode 394. Coins in a Line
      1. 2.1.1. Solution1. DFS + Memorization
      2. 2.1.2. Solution2. DP
      3. 2.1.3. Solution3. Math
    2. 2.2. LintCode 395. Coins in a Line II
    3. 2.3. LintCode 396. Coins in a Line III
      1. 2.3.1. Follow up
    4. 2.4. Coin Game

DFS + Memorization

464. Can I Win

  • DFS + Memorization + Pruning
  • If there exist one way that the other one will NOT win, then I win!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def canIWin(self, maxChoosableInteger, desiredTotal):
        if maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal:
            return False
        self.memo = {}
        return self.helper(list(range(1, maxChoosableInteger + 1)), desiredTotal)

    def helper(self, nums, desiredTotal):
        key = tuple(nums)
        if key in self.memo:
            return self.memo[key]

        if nums[-1] >= desiredTotal:
            return True

        for i in range(len(nums)):
            if not self.helper(nums[:i]+nums[i+1:], desiredTotal-nums[i]):
                self.memo[key] = True
                return True

        self.memo[key] = False
        return False

293. Flip Game

1
2
3
4
5
6
7
class Solution:
    def generatePossibleNextMoves(self, s):
        res = []
        for i in range(len(s)-1):
            if s[i] == '+' and s[i+1] == '+':
                res.append(s[:i] + "-" + "-" + s[i+2:])
        return res

294. Flip Game II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canWin(self, s):
        self.memo = {}
        return self.win(s)

    def win(self, s):
        if s in self.memo:
            return self.memo[s]

        for i in range(len(s)-1):
            if s[i] == '+' and s[i+1] == '+':
                news = s[:i] + "-" + "-" + s[i+2:]
                if not self.win(news):
                    self.memo[s] = True
                    return True

        self.memo[s] = False
        return False

DP

LintCode 394. Coins in a Line

Solution1. DFS + Memorization

  • TLE
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
        def firstWillWin(self, n):
            self.memo = {}
            return self.helper(n)

        def helper(self, n):
            if n <= 2:
                return True

            if n in self.memo:
                return self.memo[n]

            if not self.firstWillWin(n-1) or not self.firstWillWin(n-2):
                self.memo[n] = True
                return True

            self.memo[n] = False
            return False

Solution2. DP

  • Time : O(n), Space : O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def firstWillWin(self, n):
        if n == 0:
            return False

        if n <= 2:
            return True

        dp = [False] * (n+1)
        dp[1] = dp[2] = True
        for i in range(3, n+1):
            dp[i] = not dp[i-1] or not dp[i-2]
        return dp[n]

Solution3. Math

1
2
3
class Solution:
    def firstWillWin(self, n):
        return bool(n % 3)

LintCode 395. Coins in a Line II

  • dp[i], preSum[i]-dp[i] represent how many i get and how many other one get!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def firstWillWin(self, values):
        n = len(values)
        if n <= 2:
            return True

        values.reverse()
        psum = self.preSum(values)

        dp = [0] * n
        dp[0] = psum[0]
        dp[1] = psum[1]
        for i in range(2, n):
            dp[i] = max(psum[i] - dp[i-1], psum[i] - dp[i-2])
        return dp[n-1] > psum[n-1] - dp[n-1]

    def preSum(self, values):
        psum = [values[0]]
        for i in range(1, len(values)):
            psum.append(psum[-1] + values[i])
        return psum

LintCode 396. Coins in a Line III

TODO!!!

Follow up

DP[i][j] represents from i-th coin to the j-th coin, the largest sum of pizza that i can pick.

  • case1 : if i take the left coin,
  1. if input[i+1] < input[j], input[i] + DP[i+1][j-1]
  2. if input[i+1] > input[j], input[i] + DP[i+2][j]
  • case2 : if i take the right coin,
  1. if input[i] < input[j-1], input[j] + DP[i][j-2]
  2. if input[i] > input[j-1], input[j] + DP[i+1][j-1]
  • Base Case:
  1. 2 coins, DP[i][i+1] = max(input[i], input[i+1])
  2. 1 coin, DP[i][i] = input[i]

Coin Game

Let us understand the problem with few examples:

  1. 5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)
  2. 8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)
    Does choosing the best at each move give an optimal solution?
  • F(i, j) represents the maximum value the user can collect from i’th coin to j’th coin.
  1. If I take Ai, Vi + min(F(i+2, j), F(i+1, j-1)
  2. If I take Ak, Vj + min(F(i+1, j-1), F(i, j-2)
    $$F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), Vj + min(F(i+1, j-1), F(i, j-2) ))$$
  • Base Cases
  1. F(i, j) = Vi If j == i
  2. F(i, j) = max(Vi, Vj) If j == i+1
Share