分糖果问题

​

描述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

\1. 每个孩子不管得分多少，起码分到一个糖果。

\2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
        // write code here
        int n = arr.size();
        vector<int> dp(n,1);
        for(int i=1;i<n;i++) {
            if(arr[i]>arr[i-1]) 
                dp[i] = dp[i-1]+1;
        }
        for(int i=n-2;i>=0;i--) {
            if(arr[i] > arr[i+1])
                dp[i] = max(dp[i+1]+1,dp[i]);
        }
        int res = 0;
        for (int u:dp) res += u;
        return res;
    }
};