各ノードのツリーと値を考えれば、どのように各パスの合計を求めることができますか？DPすべてのノードの組み合わせを合計します
A
|
B
上記のツリーには、A、B、A-B、B-Aの4つのパスがあります。 各ノードは値をそれに割り当てる必要があります：A: 3, B: 2
予想される出力は次のようになります+ 2 3 +（3 + 2）+（2 + 3）
この問題に対するナイーブ溶液を行うことですソースからターゲットへのDFS（可能な組み合わせごと）、DFS結果を加算して合計を得ることができますが、この問題はDPで効率的に解決できますが、実際にDPでの経験はあまりありません。
あなたは、各ノードはパスで表示する頻度を計算することができます：
は、（多くの）動的なプログラミングを必要としない、この1のための素晴らしい解決策があります。
A
|
B
/\
C D
|
E
葉Aのための計算、CとE非常に簡単です：ちょうどn=5ノードとの例を取ることができます。これらは、このノードで開始または終了するパスにのみ表示されます。パスAの開始と終了がAで終わっているため、2*nで2回カウントされるので、2n - 1 = 9のパスがあります（-1）。
内側のノードでは、もう少し面倒です。最初にノードDを見てみましょう。もちろんDは、すべてのパスに表示されます。開始または終了はDです。だから我々は再び2n - 1 = 9パスを持っています。しかし、現在では、Dがパスの途中に表示される場合もあります。例えば。パスA-B-D-Eにあります。これは、パスがサブツリーABCのどこかで始まりサブツリーEまたはその反対に終わる場合にのみ発生します。コンビナトリアルは、size(ABC)*size(E) + size(E)*size(ABC) = 2*size(ABC)*size(E) = 2*3*1 = 6がたくさんあることを私たちに伝えています。したがってDは正確に9 + 6 = 15パスに現れます。
ノードBの場合、それはやや難解です。再度Bから始まるまたは終わる、2n - 1 = 9のパスがあります（これは各ノードに当てはまります）。しかし、やはりBはパスの途中に現れることがあります。このためには、サブツリーA,CまたはDEのいずれかで始まり、別のパスで終了する必要があります。したがって、可能なパスは2*size(A)*size(C) + 2*size(C)*size(DE) + 2*size(DE)*size(A) = 2*1*1 + 2*1*2 + 2*2*1 = 2 + 4 + 4 = 10です。数学を少しすれば、これは(n-1)^2 - size(A)^2 - size(C)^2 - size(DE)^2と同じであることがわかります。したがって、合計でノードは9 + 10 = 19パスに現れます。
そして、計算したい値は9*value(A) + 19*value(B) + 9*value(C) + 15*value(D) + 9*value(E)です。
深さ優先検索では、すべてのサブツリーのサイズを動的プログラミングで計算し、2つの公式を使用して各ノードの外観数を計算することができます。