题目地址：

https://www.lintcode.com/problem/card-game-ii/description

一个卡牌游戏，一共$n$张牌，每个牌的成本是$c[i]$，每个牌能造成的伤害是$d[i]$。总共有$m$这么多钱，要造成至少$x$的伤害才能获胜，问是否能获胜。每个牌只能使用一次。

是个背包问题，思路是动态规划。本质上是问，在给定预算的情况下能达到的最大伤害是多少。设$f[i][j]$表示只从$c[0:i]$里选，给定预算是$j$的情况下，所能达到的最大伤害。那么所有的方案可以分为，选$c[i]$和不选$c[i]$，所以：$$f[i][j]=\max \{f[i-1][j],f[i-1][j-c[i]]+d[i]\}$$初始条件是：$$f[0][j]=\{\begin{array}{l}0,j<c[0]\\ d[0],j\ge c[0]\end{array}$$代码如下：

public 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 */ public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) { // Write your code here int[][] dp = new int[cost.length][totalMoney + 1]; for (int i = 0; i <= totalMoney; i++) { if (i >= cost[0]) { dp[0][i] = damage[0]; } } for (int i = 1; i < cost.length; i++) { for (int j = 0; j <= totalMoney; j++) { dp[i][j] = dp[i - 1][j]; if (j >= cost[i]) { dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - cost[i]] + damage[i]); } // 如果算出可以达到要求的伤害了，直接返回true if (dp[i][j] >= totalDamage) { return true; } } } return false; } }

时空复杂度$O(l_{c}m)$。

考虑空间优化。由于$f[i][j]$只取决于上一行的值，所以可以在原数组上更新，但需要注意更新的时候要从右向左更新。代码如下：

public 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 */ public boolean cardGame(int[] cost, int[] damage, int totalMoney, int totalDamage) { // Write your code here int[] dp = new int[totalMoney + 1]; for (int i = 0; i <= totalMoney; i++) { if (i >= cost[0]) { dp[i] = damage[0]; } } for (int i = 1; i < cost.length; i++) { // 每行从右向左更新 for (int j = totalMoney; j >= 0; j--) { if (j >= cost[i]) { dp[j] = Math.max(dp[j], dp[j - cost[i]] + damage[i]); } if (dp[j] >= totalDamage) { return true; } } } return false; } }

时间复杂度不变，空间$O(m)$。