CFR 9 D. How many trees? ( DP )

Problem - D - Codeforces

題意：
問 N 個節點組成的二叉樹，深度不少於 H 的方案有幾種。

資料規模：
H ≤ N ≤ 35

解法：
dp[ i ][ j ] : N 個節點的二叉樹，深度等於 H 的方案數
兩種轉移，首先當前的根是一定要的，一種是左空或又空，另一種是兩個都非空。

時間 / 空間複雜度：
O( N^4 ) / O( N^2 )

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 35;

int N, H;
ll dp[ MAXN + 1 ][ MAXN + 1 ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N >> H;
  dp[ 0 ][ 0 ] = dp[ 1 ][ 1 ] = 1;
  for( int i = 2; i <= N; ++i ){
    for( int j = 1; j <= N; ++j ){
      dp[ i ][ j ] += dp[ i - 1 ][ j - 1 ] * 2;
      for( int k = 1; k <= i - 2; ++k ){
        for( int h = 1; h < j - 1; ++h ){
          dp[ i ][ j ] += dp[ i - 1 - k ][ h ] * dp[ k ][ j - 1 ];
          dp[ i ][ j ] += dp[ i - 1 - k ][ j - 1 ] * dp[ k ][ h ];
        }
        dp[ i ][ j ] += dp[ i - 1 - k ][ j - 1 ] * dp[ k ][ j - 1 ];
      }
    }
  }
  ll ans = 0;
  for( int i = H; i <= N; ++i ){
    ans += dp[ N ][ i ];
  }
  cout << ans << endl;
  return 0;
}