记忆化搜索

f(i)表示第i个位置至少要多少个糖果，计算f(i)的时候只需要向左看一眼再向右看一眼，如果当前点比其相邻点大就是相邻点的最小糖果数 + 1。

时间复杂度

一共计算了n个状态，每次计算的时候需要常数的时间转移，时间复杂度为O(n)

代码

class Solution {
public:
    int search(int i, vector<int>& ratings, vector<int>& f){
        if(f[i]) return f[i];
        int res = 1;
        if(i > 0 && ratings[i] > ratings[i - 1]) 
            res = max(res, search(i - 1, ratings, f) + 1);
        if(i < ratings.size() - 1 && ratings[i] > ratings[i + 1])
            res = max(res, search(i + 1, ratings, f) + 1);
        return f[i] = res;
    }
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        vector<int> f(n);
        int res = 0;
        for(int i = 0; i < ratings.size(); i++)
            res += search(i, ratings, f);

        return res;
    }
};