變換樹的K葉以最小的成本

Question

我給一棵樹，我不得不刪除節點具有k葉變換樹。每個節點都有一個與之相關的權重。刪除節點將花費相關的權重。我想盡量減少成本。

這裏是鏈接到problem-：

我不能夠以可視化的解決方案。我需要一些幫助。如果有人能夠以廣泛的方式解釋或提供一些文件將會有所幫助。

Answer 1

這裏是你如何能做到這一點的想法（你可能需要修改，並添加了一些東西，使其工作） -

如鏈接解釋，我們將使用一個二維數組，表示DP ，存儲我們的部分答案，並使用它們來查找所需的答案。其次，dp[v][k]將表示具有根節點（子樹或主樹）v我們需要確切地說是k葉節點。

基本情況 -

對於任何一個葉子結點LV-

//Case 1 - only one leaf is required so we dont need to delete any node 
dp[lv][1] = 0 

//Case 2 - more than 1 leaf node required which is not possible 
dp[lv][k] = INT_MAX 

對於任何節點U -

//As no leaf is required we delete all nodes 
dp[v][0] = sum of weights of all nodes in subtree with v(including weight of v) 

的DP-

現在讓我們力學SA Ÿ我們目前位於節點v，並且我們需要在此節點的子樹中具有葉子k。讓我們先寫下它的代碼，然後再解釋它是如何工作的。

for(int i=0;i<=k;i++) 
    dp[v][k] = min(dp[v][k], dp[left-child][i] + dp[right-child][k-i]; 

這裏left-child和right-child留和v正確的節點。

對於每個葉節點，有兩件事情是可能的，即它可以在左子樹或右子樹中。所以，我在所有這些國家從迭代不含葉節點包含所有葉子節點和同爲右子樹的左子樹左suubtree開始。最後，存儲從dp[v][k]中迭代得到的最小值。