Leetcode 動(dòng)態(tài)規(guī)劃 Candy

本文為senlie原創(chuàng)，轉(zhuǎn)載請(qǐng)保留此地址：http://blog.csdn.net/zhengsenlie

題意：n 個(gè)小孩，每個(gè)小孩有一個(gè)評(píng)分。給小孩發(fā)糖。要求：
1)每個(gè)小孩至少一顆糖
2)評(píng)分高的小孩發(fā)的糖比他旁邊兩個(gè)小孩的多
思路：左右 dp
用一個(gè)數(shù)組 candy[n]，表示第 i 個(gè)小孩所應(yīng)該發(fā)的最少糖果數(shù)
數(shù)組 ratings[n] 表示每個(gè)小孩的評(píng)分
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)

復(fù)雜度： 時(shí)間 O(n)， 空間 O(n)

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)