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

细节有点折磨人,改了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;
    }
};