Candy

题目描述：

有n个小孩站成一排，每个小孩有一个权值。你给小孩糖果要满足下面两个条件：

1. 每个小孩至少有一个糖果 2. 权值大的小孩得到的糖果比与他相邻的小孩多。

你至少要给出多少个糖果？

分析：要求满足条件1，所以我们首先给每个小孩分配糖果。为了满足条件2，我们先正向遍历，如果当前小孩的权值比前一个大，该小孩的糖果数为前一个小孩的糖果数加1，小于或等于的情况先不管；然后反向遍历，如果当前小孩的权值比后一个大，并且该小孩的糖果数小于或等于后一个小孩的糖果数，则该小孩的糖果数为后一个小孩的糖果数加1。具体代码如下：

 1 int candy(vector<int>& ratings) {
 2         int n=ratings.size();
 3         vector<int> dp(n,1);
 4         for(int i=1;i<n;i++)
 5         {
 6            if(ratings[i]>ratings[i-1])
 7              dp[i]=dp[i-1]+1;
 8         }
 9         for(int j=n-2;j>=0;j--)
10         {
11             if(ratings[j]>ratings[j+1])
12             {
13               if (dp[j] <= dp[j+1])
14                 dp[j] = dp[j + 1] + 1;
15             }
16         }
17         int sum=0;
18         for(int k=0;k<n;k++)
19         {
20             sum+=dp[k];
21         }
22         return sum;
23     }