私はツリーを与えられ、kリーフでツリーを変換するノードを削除する必要があります。各ノードには、それに関連付けられた重みがあります。ノードを削除すると、関連する重みがかかります。私はコストを最小限に抑えたい。ここで最小コストでKリーフを持つツリーを変換する
はproblem-へのリンクです：
私は解決策を視覚化することはできませんよ。助けが必要です。誰かが広範に説明したり、何らかのドキュメンテーションを提供してくれれば助けになるだろう。ここで
は、あなたがそれを行うことができる方法のアイデア（あなたはそれを操作できるようにするいくつかのことを変更し、追加する必要があります）です -
としては、リンクで説明し、我々はDPを言って、2次元配列を使用します。私たちの部分的な答えを保存し、それを使って必要な答えを見つけること。第2に、dp[v][k]は、（サブツリーまたはメインツリーの）ルートノードで、vを正確に示すことを意味します。kリーフノード。
基本ケース - 任意のノードvについては
//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
LV-任意のリーフノードの場合
- DP-
の
//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)
力学今すぐことができますsa現在、私たちはノードであり、現在であり、このノードのサブツリーに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-childVの左と右のノードです。
すべてのリーフノードには、左サブツリーまたは右サブツリーになる可能性のあるものが2つあります。ですから、私は、これらのすべての状態を、リーフノードを含まないleft-suubtreeから、すべてのリーフノードを含むleft-subtreeからright-subtreeについても繰り返しています。最後に、反復処理で見つかった最小値をdp[v][k]に格納します。