【笔记】卡牌游戏（01背包问题）

538. 卡牌游戏 II

你跟你的朋友在玩一个卡牌游戏，总***有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点伤害。

-------------------------来源于:LintCode

此题是01背包问题的变形，有关01背包问题的介绍如下：

源码如下：

def cardGame(cost, dam, tm, td):

l, m= len(cost), [0] * (tm + 1)

for iin range(l):

for jin range(tm, cost[i] - 1, -1):

m[j] = max(m[j], m[j- cost[i]] + dam[i])

if m[j] >= td:

return True

return False