变换树的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]中迭代得到的最小值。