本文例题来自135-Candy

先看题

135-Candy

理解

首先需求的条件有两个，第一个非常好理解，总糖果量至少是N，即孩子的数量。第二个条件就有点难了，我们先假设第n个孩子分得的糖果数量是f(n) 1<=n<=N，分数是r(n) 1<=n<=N，那么化为数学问题，即

if r(n) > r(n-1) then
    need f(n)>f(n-1) 
if r(n) > r(n+1) then
    need f(n)>f(n+1) 

再加上条件求得需要准备最少的糖果数量，简单讲need f(n)>f(n-1)换成f(n)=f(n-1)+1即可，所以最简单的解法也就顺势出来了。

个人的解法

#!/usr/bin/python3
class Solution:
    def candy(self, ratings: List[int]) -> int:
        sum = len(ratings)#条件一
        rat_lan = sum
        tmp =[0]*rat_lan#初始化
#if r(n) > r(n-1) then
#    need f(n)>f(n-1) 
        for i in range(1,rat_lan):
            if ratings[i] > ratings[i-1] and tmp[i] <= tmp[i-1]:
                tmp[i] = tmp[i-1]+1
#if r(n) > r(n+1) then
#    need f(n)>f(n+1) 
        for i in range(rat_lan-2,-1,-1):
            if ratings[i] > ratings[i+1] and tmp[i] <= tmp[i+1]:
                tmp[i] = tmp[i+1]+1
        for a in tmp:
            sum+=a
        return sum

学习评论

大多数解法就是用的本文的解法，毕竟好理解。

但是发现一只独秀

qmx521125
动态规划，一次遍历
C++

好吧大佬，来理解一下，话说这题能提炼出动态规划也是强。
long time age
好吧，噱头，不能叫做动态规划
不过倒是一次遍历的方法，归纳如下：
1.正序遍历当遇到等值时：f(n)=1即可
2.正序遍历当遇到顺序递增时：f(n) = f(n-1)+1
3.正序遍历当遇到顺序递减时：问题来了，如果递减的数量大于之前一个递增的数量，无法预估上一个递增的最大值？解决方案：

• 发现开始递减时，记录上一个 递增的长度
• 记录递减的长度
• sum值的计算改为增加 递减的长度

• 当 递减的长度 >= 上一个 递增的长度 时 递减的长度 的额外加一，其实就是把递增和递减公用的数，算到递减的长度里面去了
  具体如下，为嘛说不是动态规划呢，因为子问题（1个人到N个人）是有，但是不是建立在子问题之上求大问题（sum(n)与sum(n-1)没有绝对的逻辑关系）的解。

  
  一次循环

一次遍历的另一种方法

非常简单用两个tmp数组，一个正序，一个逆序，只是相当于把最初的方法整合了。