Leetcode 動態規劃 Candy

本文為senlie原創，轉載請保留此地址：http://blog.csdn.net/zhengsenlie

題意：n 個小孩，每個小孩有一個評分。給小孩發糖。要求：
1)每個小孩至少一顆糖
2)評分高的小孩發的糖比他旁邊兩個小孩的多
思路：左右 dp
用一個數組 candy[n]，表示第 i 個小孩所應該發的最少糖果數
數組 ratings[n] 表示每個小孩的評分
1.從左到右掃描一遍， candy[i] = 1, if ratings[i] <= ratings[i-1] ; candy[i] = candy[i-1] + 1, if ratings[i] > ratings[i-1]
2.從右到左掃描一遍， candy[i] = candy[i], if ratings[i] <= ratings[i+1] ; candy[i] = max(candy[i], candy[i+1] + 1), if ratings[i] > ratings[i+1]
3.accumulate(candy, candy + n, 0)

復雜度： 時間 O(n)， 空間 O(n)

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈