1. 题目

读题

游戏角色, 有技能列表和魔法值, 求能造成的最大伤害, 例如:

输入skill_list: [{mana_cost:10,damage:10}, {mana_cost:12,damage:13}], current_mana: 20, 输出max_damage: 20

输入skill_list: [{mana_cost:10,damage:10}, {mana_cost:12,damage:13}], current_mana: 25, 输出max_damage: 26

输入skill_list: [{mana_cost:2,damage:5}, {mana_cost:4,damage:11}, {mana_cost:7,damage:20}], current_mana: 13, 输出max_damage: 36

考查点

 这是一道动态规划-背包问题：完全背包问题

2. 解法

思路

和  7-010-(LeetCode- 322) 零钱兑换 是非常类似的一道题

定义dp[i] 表示： 魔法值 小于等于i 的最大伤害是多少

• 初始值： dp[0]=0 ,表示0 魔法值，最大伤害为0
• 状态转移公式：dp[i] = dp[i-cost] +damage

代码逻辑

具体实现

public class GameMaxDamage {

    public static void main(String[] args) {
        Map<Integer, Integer> test = new HashMap<>();
        test.put(2, 5);
        test.put(4, 11);
        test.put(7, 20);
        System.out.println(maxDamage(test, 13));

        Map<Integer, Integer> test2 = new HashMap<>();
        test2.put(10, 10);
        test2.put(12, 13);
        System.out.println(maxDamage(test2, 25));

        System.out.println(maxDamage(test2, 20));
    }


    public static int maxDamage(Map<Integer, Integer> map, int currentMana) {

        Set<Integer> manaCosts = map.keySet();

        int[] dp = new int[currentMana + 1];
        dp[0] = 0;

        for (Integer cost : manaCosts) {
            int damage = map.get(cost);
            for (int i = cost; i <= currentMana; i++) {
                if (i >= cost) {
                    dp[i] = Math.max(dp[i], dp[i - cost] + damage);
                }

            }
        }
        return dp[currentMana];

    }
}

3. 总结