本文例题来自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数组，一个正序，一个逆序，只是相当于把最初的方法整合了。
