6
leetCode解题报告之Candy（简单回溯）
source link: https://blog.csdn.net/ljphhj/article/details/22146837
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode解题报告之Candy（简单回溯）
题目：
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?
分析：
题目的意思是，有N个小孩子，他们都有一个rating值，小孩子站成一排，这时候rating值按顺序放入到数组中，
主人公要给N个小孩子发糖果，但是又抠门，想要尽量最少的糖果被发出！要满足如下两个条件：
1、每个孩子最少都要有一个糖果
2、拥有比较高的rating值的孩子要比自己身边的孩子得到的糖果多
解题思路：
由于这两个条件，我们需要考虑到如果rating值和相邻两边的rating值相等的情况，我们只需分配1个糖果给这个孩子就可以了
如：ratings = {1,2,2,2,3,2,1};
我们最少要分配的糖果candys = {1,2,1,1,3,2,1} = 11个糖果
但是我们如果想要确定ratings 数组中 rating值为“3”的这位孩子所得到的糖果，我们又必须知道后面的情况，所以我们需要用到回溯法.具体看如下AC代码：
AC代码：
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK