Leetcode 动态规划 Candy

时间:2021-02-02 13:50:08

本文senlie原版的,转载请保留此地址:http://blog.csdn.net/zhengsenlie

Candy

Total Accepted: 16494 Total
Submissions: 87468My Submissions

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<int> &ratings){
int n = ratings.size();
vector<int> 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);
}

版权声明:本文博主原创文章。博客,未经同意不得转载。