题目地址:
https://www.lintcode.com/problem/candy/description
给定一个数组,代表每个小朋友的评分。现在要给每个小朋友分糖果,规则是,每个小朋友至少要分得 1 1 1个糖果,并且如果某个小朋友的评分比他相邻的小朋友评分高,那么他就应该比他相邻的那个小朋友得到的糖果更多。问总共至少需要多少个糖果。
参考https://blog.csdn.net/qq_46105170/article/details/108633071。代码如下:
public class Solution {
/**
* @param ratings: Children's ratings
* @return: the minimum candies you must give
*/
public int candy(int[] ratings) {
// write your code here
int res = 0;
int[] dp = new int[ratings.length];
for (int i = 0; i < ratings.length; i++) {
res += dfs(i, dp, ratings);
}
return res;
}
private int dfs(int i, int[] dp, int[] ratings) {
// 如果有记忆则调取记忆
if (dp[i] != 0) {
return dp[i];
}
int len = 1;
// 向左拓展
if (i > 0 && ratings[i] > ratings[i - 1]) {
len = Math.max(len, 1 + dfs(i - 1, dp, ratings));
}
// 向右拓展
if (i < ratings.length - 1 && ratings[i] > ratings[i + 1]) {
len = Math.max(len, 1 + dfs(i + 1, dp, ratings));
}
// 做记忆
dp[i] = len;
return len;
}
}
时空复杂度 O ( n ) O(n) O(n)。