题目：
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻的孩子中，评分高的孩子必须获得更多的糖果。 那么这样下来，老师至少需要准备多少颗糖果呢？ 示例1: 输入: [1,0,2] 输出: 5 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例2: 输入: [1,2,2] 输出: 4 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
解题思路：
本题是一道动态规划题。主要方法是分别从左往右和从右往左遍历。
如果后一个比前一个大，那就+1；如果不是，则取1（因为最少要分配1个）。
需要注意的是遇“山峰”时，需要判断大小，比如：[1,2,3,4,2,1]，从左往右到山峰“4”的值是4，而从右往左到山峰“4”的值是3，这时应该取4。如果不加判断，逆向遍历的时候就会用3覆盖掉之前的4！
具体代码（Java）：
/**分配糖果**/ public int candy(int[] ratings) { int candy_num = 0; //糖果总数 Integer[] num = new Integer[ratings.length]; num[0] = 1; //从左往右遍历 for(int i=1;i<ratings.length;i++) { if(ratings[i] > ratings[i-1]) { num[i] = num[i-1]+1; }else { num[i] = 1; } } //从右往左遍历 for(int i=ratings.length-1;i>0;i--) { if(ratings[i-1] > ratings[i] && num[i]+1>num[i-1]) { num[i-1] = num[i]+1; } } for(Integer i:num) { candy_num += i; } return candy_num; }
