注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。

本文阅读时间约为5分钟。

递归编程练习题5：分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。

相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

输入格式:

一个列表，以文本格式的有效Python表达式给出。

输出格式：

一行数字，表示满足分配条件所需的最少糖果数。

输入样例：

[1,2,2]

输出样例：

4

注：可行的分配方案为1、2、1 颗糖果；第三个孩子只得到1颗糖果也满足题目条件。

示例代码模板：

def candy(ratings):
    # code here
    pass
 
lst = eval(input())
print(candy(lst))

解答：本题要求的是，在符合规则的前提下，所有孩子分得的糖果数量最小，所以评分高的孩子比相邻评分低的孩子多分得的糖果数多得尽量少，比如多1个。

但是题意明确要求即使坠最低得分的孩子也要分得至少1个糖果。难点在于，因为不确定相邻孩子后面的得分是怎样的，因此会发生评分高的孩子得糖果数不够情况。

双向遍历是解决这个问题的关键。

参考代码及相关注释如下：

# 递归编程练习题：分发糖果。
def candy(ratings):
    '''
    ratings：元素为每个孩子评分的列表。list类型。
    '''
    candies = [1] * len(ratings)  # 建立一个孩子分的糖果的列表容器，每个孩子初始得到的糖果数都是1。
    
    # 正向遍历孩子的评分列表ratings，比相邻孩子评分更高的孩子分更多糖果。
    for i in range(len(ratings) - 1):
        if ratings[i] < ratings[i + 1]:
            candies[i + 1] = candies[i] + 1
    
    # 反向遍历孩子的评分列表ratings，比相邻孩子评分更高的孩子分更多糖果。
    for i in range(len(ratings) - 1, 0, -1):
        if ratings[i] < ratings[i - 1] and candies[i - 1] <= candies[i]: 
            candies[i - 1] = candies[i] + 1
    
    # 经过正反两道遍历之后，得出的candies列表即为孩子的最后分得糖果数的列表。
    return sum(candies) # 用sum函数对列表中的所有元素直接进行求和，一步到位。

lst = eval(input())
print(candy(lst))

<<<
[1, 2, 3, 4, 1, 2, 4, 2, 1]
19
<<<

To be continued.