天池 在线编程 卡牌游戏（01背包）

样例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点伤害。

class Solution {
public:
    /**
     * @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
     */
    bool cardGame(vector<int> &cost, vector<int> &damage, int totalMoney, int totalDamage) {
        // Write your code here
        int n = cost.size();
        unordered_map<int,int> dp;
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            unordered_map<int,int> tmp(dp.begin(), dp.end());//复制上一次的状态，这次不拿
            for(auto& d : dp) { // 遍历原有状态
                int c = d.first;
                int dg = d.second;
                if(c + cost[i] <= totalMoney)// 可以拿
                {
                    tmp[c + cost[i]] = max(tmp[c+ cost[i]], dg+damage[i]);
                    if(tmp[c + cost[i]] >= totalDamage)
                        return true;
                }
            }
            dp.swap(tmp);
        }
        return false;
    }
};