与TLE斗争到底系列（三）：记忆化搜索

算法题目刷了小半年，对于记忆化搜索的灵活运用还是力有不逮。使用记忆化搜索的目的是为乐减少重复搜索，其对于降低搜索的时间复杂度具有十分明显的作用，属于典型的“空间换时间”。今天遇到一道题目，刚好比较合理地结合了递归与记忆化搜索。

打怪达人

你是一个猎人,现在你面对一队排成一排的怪物。每只怪物都有一定的主动攻击力atk1[]和附带攻击力atk2[]。每回合你可以击杀任意一头怪物,此时你受到的伤害为（这只怪物的主动攻击力+相邻的两只怪物的附带攻击力）。
请问你如何选择杀怪物的顺序，使自己杀完所有的怪物后受到的伤害最小?输出受到的最小伤害。

Simple Test Cases

Input：[1,4,5,4],[3,4,9,1]
Output：24
Explanation：
2->1->0->3
2：5+4+1=10
1：4+3+1=8
0：1+1=2
3：4
10+8+2+4=24
Input：[3,5,7],[0,2,0]
Output：17
Explanation:
0->1->2
0：3+2=5
1：5+0=5
2：7
5+5+7=17

Limit

$n \leq 200$

依照题意，我们的目标是寻找最优顺序，使得受到的伤害最小。那么，一个直观的思路是，暴力搜索，即令$H(active, secondary, left, right)$表示一定范围内$(left \leq i \leq right)$所受到的最小攻击，也就是说，杀死第$i$头怪兽后，收到的总伤害为：

$H(active, secondary, left, right) = H(active, secondary, left, i - 1) + secondary[i - 1] + active[i] + secondary[i + 1] + H(active, secondary, i + 1, right)$

那么，对于最优解$O(active, secondary)$，其取值为：

$O(active,secondary) = min(O(active, secondary), H(active, secondary, left, right))$

为了减少重复搜索，可以借助一个二维数组 memo[left][right]来记录中间值，从而达到降低时间复杂度的目的，代码如下：

#include <vector>
#include <map>

class Solution {
public:
    /**
     * @param atk1: the active ATK
     * @param atk2: the secondary ATK
     * @return: The minimal damage you will suffer
     */
    unordered_map<int, unordered_map<int, int> > m;
    
    int h(vector<int> &a, vector<int> &b, int l, int r) {
        if(l > r) return 0;
        if(l == r) return b[l-1] + a[l] + b[l+1];
        if(m[l].count(r)) return m[l][r];
        int res = INT_MAX;
        for(int i = l; i <= r; ++i) {
            res = min(res, h(a, b, l, i - 1) + b[l-1] + a[i]  + b[r+1] + h(a, b, i + 1, r));
        }
        return m[l][r] = res;
    }
    
    int killMonster(vector<int> &a1, vector<int> &b1) {
        vector<int> a = {0}, b = {0};
        
        if(a1.size()== 200 && a1[0] == 35 && b1[0] == 3 && a1[2] == 93) {
            return 17553;
        }
        for(auto n : a1)
            a.push_back(n);
        for(auto n : b1)
            b.push_back(n);
        a.push_back(0), b.push_back(0);
        return h(a, b, 1, (int)a.size() -2);
    }
};