如何確定訪問有根樹的k離開節點的最小步驟？

Question

該算法即將訪問k個離開節點並以最小步數返回到根節點！

認爲這是作爲一個人站在2點，他/她想要訪問的最基本的步驟樹中的k樹葉和回點2

對於k = 3路徑可就像

2->「3」→2→1->「0」→1→「5」→1→2（這裏3,0,5是葉子） 所以我們訪問了3個leves ..

答案：8

Answer 1

這是有根樹上的又一個自下而上的動態程序。

對於每個子樹，我們計算至少訪問j樹葉的成本，作爲列表。如果子樹是單葉，則此列表是[0, 0, ∞, ∞, …, ∞]，其中∞表示無窮大，表示不可行的葉子數量。否則，我們計算每個孩子的列表，除2之外的每個列表中的第一個以外的所有條目增加，然後通過卷積減少。要卷積兩個列表A和B將計算[min {A[i] + B[j-i]: i in 0…j}: j in 0…k]。返回根的k條目。

這是O(n k^2)時間。