题解 | #牛牛打怪兽#

思路：

题目的主要信息：

数组A表示n只怪兽的血量
攻击第 $i$ 只怪兽时，必须同时打到第 $2i$ 和第 $2i+1$ 只怪兽，每次攻击一滴血（没有这三只怪兽则无法攻击）
怪兽血量归零后还可以继续受到攻击
需要使用最少多少次组合拳才能把所有怪兽打死，如果打不死请输出-1

方法一：贪心+ 迭代
具体做法：
首先，组合拳一定要打至少3只怪兽，怪兽数量小于3，无法击败；其次，攻击第 $i$ 只怪兽时，必须同时打到第 $2i$ 和第 $2i+1$ 只怪兽，因此怪兽数量一定是奇数，偶数还是无法击败。
然后我们利用贪心思想，从中间只怪兽( $n/2$ )开始，因为打中间怪兽时我们会同时攻击到最后两只怪兽，我们的目的就是优先解决最后的怪兽，选出最后两只的最大者，打这么多次便可以将这两只怪兽解决掉，能否解决掉第 $n/2$ 只怪兽我们暂时不用管，因为不断向前遍历，第 $n/2$ 只怪兽会成为其他的2倍下标，比如 $n/4$ ，后续还可以打掉，只需要记录下它还剩多少即可；如果一开始直接解决掉了第 $n/2$ 只怪兽我们也不用担心，因为后续还可以鞭尸。最后加上第一只怪兽剩余的血量就是我们所求答案。
如下图所示，其中图中后面的元素代码中可以不置为0，因为后续不会再访问，图中置为0原因是方便于观察：
图片说明
（下方代码注意下标从0开始）

class Solution {
public:
    int slove(int n, vector<int>& A) {
        if(n <= 2)   //怪兽数量不够
            return -1;
        if(n % 2 == 0) //找不到第2i+1只怪兽
            return -1;
        int res = 0;
        for(int i = n / 2 - 1; i >= 0; i--){
            int temp = max(A[2 * i + 1], A[2 * i + 2]);  //找出最大值
            A[i] = max(0, A[i] - temp); //已经被攻击了多少
            res += temp;
        }
        return res + A[0];
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一次遍历，循环到 $n/2$
空间复杂度： $O(1)$ ，常数个变量

方法二：贪心+递归
具体做法：
上述的迭代，我们也可以改成递归。
每个子问题是，求攻击第 $i$ 只怪兽时，同时击败第 $2i$ 和第 $2i+1$ 只怪兽需要的拳数，改变第 $i$ 只怪兽剩余血量后，子问题的答案往前累加。
跳出递归的点就是只剩下最后一直怪兽了，子问题为0.

class Solution {
public:
    int recursion(int n, vector<int>& A){
        int temp = max(A[2 * n + 1], A[2 * n + 2]);  //找出最大值
        A[n] = max(0, A[n] - temp); //被攻击后还剩下多少
        if(n - 1 >= 0)
            return temp + recursion(n - 1, A);  //往下递归
        else 
            return temp;
    }
    int slove(int n, vector<int>& A) {
        if(n <= 2)   //怪兽数量不够
            return -1;
        if(n % 2 == 0) //找不到第2i+1只怪兽
            return -1;
        return recursion(n / 2 - 1, A) + A[0];  //递归
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，一共递归 $n/2$ 次
空间复杂度： $O(n)$ ，递归栈深度为 $n/2$