1538. 卡牌游戏 II

中文English

你跟你的朋友在玩一个卡牌游戏，总共有 n 张牌。每张牌的成本为 cost[i] 并且可以对对手造成 damage[i] 的伤害。你总共有 totalMoney 元并且需要造成至少 totalDamage 的伤害才能获胜。每张牌只能使用一次，判断你是否可以取得胜利。

样例

样例1

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

输出: true
样例说明: 我们可以使用 [1,4,5] 去造成10点伤害，总花费为10。

Example2

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

输出: false
样例说明：我们最多只能造成7点伤害。
动态规划(背包问题1)

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, costs, damages, totalMoney, totalDamage):
        # Write your code here
        #动态规划，背包问题1
        length = len(costs)
        
        #边界情况，无牌或者是无钱
        if length == 0 or totalMoney == 0:
            return False
            
        #dp
        dp = [[0] * (totalMoney + 1) for _ in range(length + 1)]

        #计算顺序
        for i in range(length):
            for j in range(1, totalMoney + 1):
                #加入前i张表拥有的钱 < costs[i]
                if j < costs[i]:
                    dp[i][j] = dp[i - 1][j]
                else:
                    #符合条件
                    dp[i][j] = max(dp[i - 1][j - costs[i]] + damages[i], dp[i - 1][j])
            
        #最后的dp就是最大的
        return dp[length - 1][totalMoney] >= totalDamage