There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.Children with a higher rating get more candies than their neighbors.What is the minimum candies you must give?
此题题意是：一排学生每人有一个评分，根据评分为他们分糖果，规则是：每人至少一个糖，相邻同学中，分更高的同学所分的糖果比与他相邻同学多，求最后符合条件分配结果中所分的所有糖果之和。（开始理解错了，我还以为最少那个同学几个糖，肯定是一个啊。。。）
解法是一维的动态规划，新建长度为评分数组长度的数组，所有值初始化为1，第一步处理：从左至右，如果当前同学分比前一个同学分高，他的糖果数比前一个同学多一个；第二步处理：从右至左，如果当前同学分比后一个同学高且糖比他后面同学少，那么他的糖果数是后一个同学糖果数加一；最后计算数组所有元素和。代码如下：
class Solution { public: int candy(vector<int>& ratings) { if(ratings.empty()) return 0; vector<int> candys(ratings.size(), 1); int result = 0; for(int i=1; i<candys.size(); ++i) if(ratings[i] > ratings[i-1]) candys[i] = candys[i-1]+1; for(int i=candys.size()-2; i>=0; --i) if(ratings[i] > ratings[i+1] && candys[i] <= candys[i+1]) candys[i] = candys[i+1]+1; for(int i=0; i<candys.size(); ++i) result += candys[i]; return result; } };
