主題
題目連結：
題目意譯：
你被給定一個整數 hoursBefore ，代表你到達會議的時限。為了抵達會議，你必須行經過 n 條路。路的長度被給定為一長度為 n 個整數陣列 dist ，其中 dist[i] 代表第 i 條路的公里數。此外，你被給定一整數 speed ，其為你將會行駛的速度（每小時公里數）。
在你行經過路段 i 後，你必須休息並等待到下一個整數小時才能啟程到下一個路段。注意，你行駛過最後一個路段後不需要休息，因為你已經到達會議了。
例如，如果行駛某段路花費了 1.4 小時，則你必須等到 2 小時時間點才能往下一個路段。如果行駛某段路花費恰好 2 小時，則你不需要等待。
不過，你被允許跳過某些休息片段以便準時抵達，代表著你不需要等待到下一個整數小時。注意，這意味著你行駛未來的路段可能結束於不同的時間點。
例如，假設行駛第一條路需耗費 1.4 小時，而行駛第二條路需要花費 0.6 小時。跳過第一條路後的休息片段意味著你行駛第二條路將結束於 2 小時之時間點，使得你可以立即前往第三個路段。
回傳準時抵達所需最小跳過休息片段之次數。如果不可能則回傳 -1 。
限制：
n == dist.length
1 ≦ n ≦ 1000
1 ≦ dist[i] ≦ 10 ^ 5
1 ≦ speed ≦ 10 ^ 6
1 ≦ hoursBefore ≦ 10 ^ 7
範例測資：
範例 1：
輸入： dist = [1,3,2], speed = 4, hoursBefore = 2
輸出： 1
解釋：
在不跳過任何休息的情況下，你將抵達於 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小時。
你可以跳過第一次休息並抵達於 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小時。
注意第二次休息被縮短了，因為你行駛第二條路段因跳過第一次休息而結束於整數小時時間點。
範例 2：
輸入： dist = [7,3,5,5], speed = 2, hoursBefore = 10
輸出： 2
解釋：
在不跳過任何休息的情況下，你將抵達於 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小時。
你可以跳過第一和第三次休息並抵達於 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小時。
範例 3：
輸入： dist = [7,3,5,5], speed = 1, hoursBefore = 10
輸出： -1
解釋： 即便你跳過所有休息片段，你仍無法準時抵達會議。
解題思維：
首先我們要先避免處理浮點數（避免誤差，儘管可以額外修正）。
因為距離 ÷ 速度 = 時間，所以距離 = 時間 × 速度。因此我們的距離「總和」（不是直接的所有距離之總和，因為本題有「休息」之規則）不應超過 hoursBefore × speed 。超過便代表著現在的狀態無法準時抵達。
而「休息」的規則怎麼辦呢？假設你現在距離「總和」為 d ，則要不要休息即是代表著 d 是否可以被 speed 整除。如果可以整除就不需休息（整數小時時間點）；反之，則需補正為最接近 d 、值 > d 且為 speed 的倍數之數字，而該數即為 d + speed - (d % speed) 。其中「%」代表取餘之操作。
因此我們定義 Adjust(d) 代表為套用以上補正規則來表示「休息」後的距離「總和」。
（為了方便起見之故，以下的 dist 陣列之索引值從 1 開始數。從 0 開始則需將下列的 i 值全數替換成 (i + 1)）
我們定義 D[i][j] ，代表行駛完第 i 條路（dist[1] ～ dist[i]，i ≧ 1）其間跳過 j 次休息片段所可能花費的最少時間。而我們可以看到其遞迴式：
D[i][j] = min(Adjust(D[i-1][j] + dist[i]), D[i-1][j-1] + dist[i])
其中 min() 代表取其中的最小值。而 min() 中的第一項代表著不跳過第 i 次路段的休息（所以要呼叫 Adjust() 作調整）、第二項則代表要跳過第 i 次休息（因此不用呼叫 Adjust()）。
而初始狀態為 D[0][0] = 0 、 D[i][0] = Adjust(D[i-1][0] + dist[i]) （對於 i ≧ 1）。
有了初始狀態之後，就仿照其他動態規劃（Dynamic Programming）之題目——從 D[1][0] 推得 D[1][1]；D[2][0] 推得 D[2][1] 、 D[2][2] 等等。
最後我們從 D[dist.length][0] 開始一路往 D[dist.length][dist.length-1] 跑。如果我們現在是 D[dist.length][i] ，而 D[dist.length][i] ≦ hoursBefore × speed ，則代表我們只需跳過 i 次的休息時間便可以準時抵達。而如果掃完之後都沒遇到這樣子的情形，則代表我們不可能準時抵達，因此回傳 -1 。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
