1. 題目

老師想給孩子們分發(fā)糖果，有 N 個(gè)孩子站成了一條直線，老師會(huì)根據(jù)每個(gè)孩子的表現(xiàn)，預(yù)先給他們評分。

你需要按照以下要求，幫助老師給這些孩子分發(fā)糖果：

• 每個(gè)孩子至少分配到 1 個(gè)糖果。
• 相鄰的孩子中，評分高的孩子必須獲得更多的糖果。

那么這樣下來，老師至少需要準(zhǔn)備多少顆糖果呢？

示例 1: 輸入: [1,0,2] 輸出: 5 解釋: 你可以分別給這三個(gè)孩子分發(fā) 2、1、2 顆糖果。示例 2: 輸入: [1,2,2] 輸出: 4 解釋: 你可以分別給這三個(gè)孩子分發(fā) 1、2、1 顆糖果。第三個(gè)孩子只得到 1 顆糖果，這已滿足上述兩個(gè)條件。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/candy
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 正反遍歷，分別考慮左邊和右邊
• 最后取兩者的較大者

class Solution { // C++ public:int candy(vector<int>& ratings) {int i, j, n = ratings.size(), sum = 0;vector<int> dp(n,1);for(i = 1, j = n-2; i < n && j >= 0; ++i,--j){if(ratings[i] > ratings[i-1])dp[i] = max(dp[i], dp[i-1]+1);else if(ratings[i] == ratings[i-1])dp[i] = max(dp[i], dp[i-1]);if(ratings[j] > ratings[j+1])dp[j] = max(dp[j], dp[j+1]+1);else if(ratings[j] == ratings[j+1])dp[j] = max(dp[j], dp[j+1]);}for(i = 0; i < n; ++i)sum += dp[i];return sum;} };

44 ms 17.1 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode 135. 分发糖果（DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。