ルート指向パスの最大数

Question

私はこの問題を持っています。私は再帰的メソッドで解決しなければならず、再帰的メソッドに基づいて動的プログラミングソリューションを構築しなければなりません。 私は、主に再帰的な解決に役立っていただければ幸いです。

与えられたルート木Tおよび番号K。ルート有向パスは、すべての頂点がパス内の彼の前の頂点の親であるパスであると定義される。 目標：例えばT

における長さkのルート指向経路のdinstinctの最大数（NO共通の頂点）を見つける：画像のツリーであり、k = 3のための答えは：3

example

Answer 1

uにサブツリーされたツリー内の長さがkであり、パス内にuという名前のルート指定パスの別個の（共通の頂点がない）最大数として定義します。

また、任意の経路でu NOTとuにルート付きツリーサブにおける長kのルート指向経路の別個の最大数（NO共通の頂点）としてDP_out(u,k)を定義します。

私はまずDP_out(u,k)を処理します。 uがいずれのパスにも含まれていない場合、長さkの最大ルート指向パスが、いずれかの子ルートにuのルートである必要があります。だから私たちは持っています：

DP_out(u,k)=Sum i=1 to r [max(DP_in(v_i, k-1), DP_out(v_i, k)) ]ここで、v_1, ..., v_rはuの子です。 DP_in(u,k)用として今

、uは1、その後、パスであり、かつ唯一、uの子供のはuを含むパスでなければならないからです。したがって、我々は持っている：rは、あなたのツリーのルートノードである場合

DP_in(u,k)= max (DP_in(v_i, k-1)+ Sum j=1 to r, j=/=i [max(DP_in(v_j, k-1), DP_out(v_j, k))])

i=1,...,r.以上を、そしてあなたが望む答えは、実際 max(DP_in(r,k), DP_out(r,k))です。

ツリーの最下部（葉）から同時にDPテーブルを作成して、テーブルを塗りつぶす順番が正しいことを確認できます。

我々はO(n^2)サブ問題があることを知っており、DP_in(u,k)の各部分問題は単純O(n^2)で計算することができるがDP_out(u,k)の各部分問題はO(n)に計算することができます。したがって、最悪のケースの合計はO(n^4)です。

私の方法が最も最適な方法であると主張しているわけではないことに注意してください。若干最適化された方法（DSを使用します）が多分ありますが、興味があれば追求してくださいその中に。