分糖果

因为一个小朋友分得最少的情况与他旁边两个小朋友👬都有关🐶，因此需要从两边扫描。

细节有点折磨人，改了4次才pass，呵呵哒。

注意三个问题：

1. 扫描的循环开始值，与终止条件，一般来说正着敦不容易出错，反着敦(如第二个循环)就容易把边界条件搞搞搞...错了
2. 需要变更dp元素的情况是，ratings1 = dp2(注意此处等于号)
3. 变更不能++dp[i]，而需要在另一个元素的基础上+1

//
// Created by jt on 2020/8/9.
//
class Solution {
public:
    /**
     *
     * @param ratings int整型vector
     * @return int整型
     */
    int candy(vector &ratings) {
        // write code here
        // 设f(i)为第i个小朋友最少分到的糖果🍬数量，则f(i)与f(i-1)和f(i+1)有关
        // 于是从两边分别扫描dp数组
        int size = ratings.size();
        vector dp(size, 1);
        for (int i = 1; i < size; ++i) {
            if (ratings[i] > ratings[i - 1] && dp[i] <= dp[i - 1]) dp[i] = dp[i-1] + 1;
        }
        for (int i = size - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1] && dp[i] <= dp[i + 1]) dp[i] = dp[i+1] + 1;
        }
        int sum = 0;
        for (int i = 0; i < size; ++i) {
            sum += dp[i];
        }
        return sum;
    }
};