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.
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