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?

**Understand the problem:**

This is a assigning candy problem. There are basically two requirements. First of all, each child must have at least one candy. Secondly, children with a higher rating get more candies than their lower rating neighbor. We can take several examples to show this problem.

For 1 2 3 3 3

1 2 3 1 1 , so sum = 8

For 1 2 3 2 3

1 2 3 1 2 so sum = 9

Note that we cannot sort the array, since we must maintain the neighbor relationships between each child. So we can naturally think of using DP to solve this problem.

**A DP Solution:**

- Define a DP array, dp[N], where as dp[i] means number of candies for child i.
- Transit function:

**A better solution:**

public class Solution { public int candy(int[] ratings) { if (ratings == null || ratings.length == 0) { return 0; } int[] candy = new int[ratings.length]; Arrays.fill(candy, 1); for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { candy[i] = candy[i - 1] + 1; } } for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { candy[i] = Math.max(candy[i], candy[i + 1] + 1); } } int sum = 0; for (int i = 0; i < ratings.length; i++) { sum += candy[i]; } return sum; } }

## No comments:

## Post a Comment