pylist

1538. Card Game II

You are playing a card game with your friends, there are n cards in total. Each card costs cost[i] and inflicts damage[i] damage to the opponent. You have a total of totalMoney dollars and need to inflict at least totalDamage damage to win. And Each card can only be used once. Determine if you can win the game.

Example1

Input:
cost = [1,2,3,4,5]
damage = [1,2,3,4,5]
totalMoney = 10
totalDamage = 10

Output: true
Explanation: We can use the [1,4,5] to cause 10 damage, which costs 10.

Example2

Input:
cost = [1,2]
damage = [3,4]
totalMoney = 10
totalDamage = 10

Output: false
Explanation: We can only cause 7 damage at most.

Solution

class Solution:
    """
    @param cost: costs of all cards
    @param damage: damage of all cards
    @param totalMoney: total of money
    @param totalDamage: the damage you need to inflict
    @return: Determine if you can win the game
    """
    def cardGame(self, cost, damage, totalMoney, totalDamage):
        # variable to store answers
        # dp[i][y] is the answer of questions:
        #   find the max damage given
        #   first i card, i = 0 : len(cost)
        #   with available money y, y = 0 : totalMoney
        dp =[[0]*(1+totalMoney) for i in range(len(cost)+1)]
        # dp[0]: keep as is
        # dp[1] ~ dp[-1]
        for i in range(1, 1+len(cost)):
            for y in range(1, 1+totalMoney):
                if cost[i-1] > y:
                    dp[i][y] = dp[i-1][y]
                else:
                    dp[i][y] = max([
                        dp[i-1][y],
                        damage[i-1] + dp[i-1][y-cost[i-1]]
                        ])
                if dp[i][y] >= totalDamage:  # equal is important
                    return True
        return False