SRM401 Div2 Medium

500

図がいまいち理解できなかった。

class FIELDDiagrams {
public:
  long long countDiagrams(int fo)
  {
    const int N = 30 + 2;
    lli dp[N][N];
    fill(&dp[0][0], &dp[N - 1][N], 0);

    dp[1][0] = 1;
    dp[1][1] = 1;

    for (int i = 0; i < fo; ++i) {
      for (int j = 0; j <= i; ++j) {
        for (int k = j; k <= i + 1; ++k) {
          dp[i + 1][k] += dp[i][j];
        }
      }
    }

    lli sum = 0;
    for (int i = 1; i <= (int)fo; ++i) {
      sum += dp[fo][i];
    }
    return sum;
  }
};