【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?

 1 class Solution {
 2 public:
 3     int candy(vector<int> &ratings) {
 4         int result = 0;
 5         vector<int> candy(ratings.size(), 0);
 6         for (int i = 0; i < ratings.size(); ++i) {
 7             result += solve(ratings, candy, i);
 8         }
 9         return result;
10     }
11 private:
12     int solve(vector<int> &ratings, vector<int> &candy, int i) {
13         if (candy[i] != 0) return candy[i];
14         candy[i] = 1;
15         if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1]) {
16             candy[i] = max(candy[i], solve(ratings, candy, i + 1) + 1);
17         } 
18         if (i > 0 && ratings[i] > ratings[i - 1]) {
19             candy[i] = max(candy[i], solve(ratings, candy, i - 1) + 1);
20         }
21         return candy[i];
22     }
23 };

View Code

先把所有小孩分得的糖初始化为1，然后当糖的数目不能满足左右两边的约束时增加糖的数量，直到符合条件。递归求解。