135.分糖果 (dp记忆化搜索)

135.分糖果 (dp记忆化搜索)

20年下半年师兄面试做过的一道题目

思想是记忆化搜素，相关题目：Acwing里搜索滑雪

用一个数组 f 来记录当前孩子能拿到多少糖果，数组w来记录孩子的评分，一开始 f 里面的数均为-1填充，每次遍历完成以后，会记录下当前孩子拿到糖果的最大值，如果左边或者右边孩子评分比自己低，自己的得分应该是两者最低得分加一：
f[i] = max(f[i], dp(i - 1) + 1)
或
f[i] = max(f[i], dp(i + 1) + 1)
最后相加即可。

code

class Solution {
public:
vector f;
vector w;
int n = 0;
    int candy(vector& ratings) {
        n = ratings.size();
        f.resize(n, -1); // -1来判别是没有被遍历过的值
        w = ratings;
        int res = 0;
        for (int i = 0; i < ratings.size(); i++) res += dp(i);
        return res;
    }
    int dp(int i) {
        if (f[i] != -1) return f[i]; //如果已经存在，则返回该值
        f[i] = 1;
        if (i && w[i - 1] < w[i]) f[i] = max(f[i], dp(i - 1) + 1);
        if (i + 1 < n && w[i + 1] < w[i]) f[i] = max(f[i], dp(i + 1) + 1);
        return f[i];
    }
};