Leetcode 動態規劃 Candy

Leetcode 動態規劃 Candy

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 個小孩，每個小孩有一個評分。給小孩發糖。要求：
  1)每個小孩至少一顆糖
  2)評分高的小孩發的糖比他旁邊兩個小孩的多
  思路：左右 dp
  用一個數組 candy[n]，表示第 i 個小孩所應該發的最少糖果數
  數組 ratings[n] 表示每個小孩的評分
  1.從左到右掃描一遍， candy[i] = 1, if ratings[i] <= ratings[i-1] ; candy[i] = candy[i-1] + 1, if ratings[i] > ratings[i-1]
  2.從右到左掃描一遍， candy[i] = candy[i], if ratings[i] <= ratings[i+1] ; candy[i] = max(candy[i], candy[i+1] + 1), if ratings[i] > ratings[i+1]
  3.accumulate(candy, candy + n, 0)
  
  復雜度： 時間 O(n)， 空間 O(n)
   

  int candy(vector &ratings){
  	int n = ratings.size();
  	vector candy(n, 1);
  	for(int i = 1; i < n; ++i){
  		candy[i] = ratings[i] <= ratings[i - 1] ? 1 : candy[i - 1] + 1;
  	}
  	for(int i = n - 2; i > -1;--i){
  		candy[i] = ratings[i] <= ratings[i + 1] ? candy[i] : max(candy[i], candy[i + 1] + 1);
  	}
  	return accumulate(candy.begin(), candy.end(), 0);
  }