1.題目

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?

2.代碼

public class Solution {public int candy(int[] ratings){int size=ratings.length;if(size<=1) return size;int[] nums=new int[size];for(int i=0;i<size;i++){nums[i]=1;}for(int j=1;j<size;j++){if(ratings[j]>ratings[j-1]) nums[j]=nums[j-1]+1;}for(int m=size-1;m>0;m--){if(ratings[m-1]>ratings[m]){nums[m-1]=Math.max(nums[m]+1,nums[m-1]);}}int result=0;for(int n=0;n<size;n++){result+=nums[n];}return result;} }

/********************************

* 本文來自博客 ?“李博Garvin“

* 轉載請標明出處:http://blog.csdn.net/buptgshengod

******************************************/

總結

以上是生活随笔為你收集整理的【LeetCode从零单排】No.135Candy(双向动态规划)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。