You are given a range [first, last], initially white. You need to paint it black. For this purpose you have a set of triples [(f, l, cost), ...] - where each triple means that you can paint range [f, l] for 'cost' coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find the minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible.
Example:
[first, last] = [0, 5] and set of triples are [[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]]. Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:
[first, last] = [0, 5] and triples are [[1, 4, 10], [2, 5, 6]]. Answer is -1.
太長(zhǎng)不翻譯。
1. 詢問
fl一定是first, last的子區(qū)間嗎踊赠？假設(shè)是。也就是說不會(huì)超出那個(gè)范圍。
2. 分析
問題探析
這道題并沒有直觀的暴力破解手段陌粹，因?yàn)橐蟮氖怯米畹蚦ost溺蕉。
一看這道題奏属，和區(qū)間還是相關(guān)跨跨，可以考慮先對(duì)區(qū)間進(jìn)行排序。首先肯定是對(duì)f進(jìn)行升序排列囱皿，至于之后需不需要對(duì)l進(jìn)行排序勇婴，還不能確定。
那么嘱腥，至少就可以看到一種解法：每次把當(dāng)前可能選取的區(qū)間都拿出來耕渴，然后進(jìn)行遞歸〉鳎可以認(rèn)為初始區(qū)間是[first, first]萨螺，每次遞歸那些f小于等于當(dāng)前區(qū)間的l的區(qū)間窄做。因?yàn)榧僭O(shè)已經(jīng)認(rèn)為不會(huì)超過范圍愧驱，因此最后結(jié)束的時(shí)候必定是以last做結(jié)尾的，這時(shí)候就可以記錄下cost椭盏。最終選擇最小的cost即可组砚。
排序是O(nlogn)。遞歸的具體時(shí)間復(fù)雜度好像很難看出來的樣子掏颊，另外空間復(fù)雜度肯定也大于O(n)糟红。
DP解法
上面那種解法屬于比較自然的解法，其實(shí)這個(gè)題也可以用DP來解乌叶。Dp[i]用來表示從first到i這個(gè)區(qū)間的最小cost盆偿。顯然題目要求的解就是Dp[last]。
可以預(yù)期的是很多Dp項(xiàng)不會(huì)有值准浴。因此其遞推公式是范圍相關(guān)的事扭。具體來說，就是在i之前的范圍里面去找l大于等于i+1的乐横，然后和Dp[i]的cost相加求橄，假如比當(dāng)前Dp[l]的cost要小今野，就替換之。為了方便挑罐农，需要對(duì)l排序条霜。這樣做的時(shí)間復(fù)雜度是O(tn)，t是區(qū)間長(zhǎng)度涵亏，n是給的triples的個(gè)數(shù)宰睡。空間復(fù)雜度是O(n)气筋。初始值就是Dp[first] = 0.
兩種解法都列出來夹厌。
3. 代碼
class Solution(object):
def sortL(self, L):
L.sort(key=lambda x: x[1])
return L
def sol(self, ranges, L, R):
seq = self.sortL(ranges)
dp = [0] + [-1] * (R)
for j in range(L + 1, R + 1):
minv = 0x7fffffff
i = len(seq) - 1
seq[i][0] = max(L, seq[i][0])
seq[i][1] = min(R, seq[i][1])
while i >= 0 and seq[i][1] >= j:
if seq[i][0] < j and dp[seq[i][0]] != -1 and dp[seq[i][0]] + seq[i][2] < minv:
minv = dp[seq[i][0]] + seq[i][2]
i -= 1
if minv == 0x7fffffff:
dp[j] = -1
else:
dp[j] = minv
return dp[R]
# solution 2
def sortF(self, F):
F.sort(key=lambda x: x[0])
return F
def sol2(self, ranges, L, R):
seq = self.sortF(ranges)
self.cost = 0x7fffffff
self.recur(seq, L, R, 0)
if self.cost == 0x7fffffff:
return -1
else:
return self.cost
def recur(self, seq, cur, R, cost):
if cur == R:
self.cost = min(self.cost, cost)
return
Q = []
for r in seq:
if r[0] <= cur:
Q.append(r)
else:
break
T = list(seq)
for r in Q:
T.remove(r)
self.recur(T, r[1], R, cost + r[2])
T.append(r)
4. 總結(jié)
難度medium~hard。
