#include<bits/stdc++.h> using namespace std; int main() { //当节点个数n确定时 能组成的二叉树结构个数也是确定的 // n个节点中1,2,...n均可做根节点 // ans = f(1) + f(2) + ... + f(n) f(i)表示当i做根节点时有几种结构 // i为根,则说明左子树有i-1个节点,右子树有n-i个节点 f(i) = f(i-1) * f(n-i) // 存在重叠子问题,可dp解决 int n; cin>>n; int mod = 1e9 + 7; vector<long>dp(n+1,0); dp[0] = 1; dp[1] = 1; for(int i=2;i<=n;++i) { for(int j=0;j<i;++j) { dp[i] += ((dp[j]%mod) * (dp[i-j-1]%mod)); dp[i]%=mod; } } cout<<dp[n]; return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { final static int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); long[] dp = new long[n + 1]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= n; i++) { for(int j = 0; j < i; j++){ dp[i] += dp[j] * dp[i - j - 1]; dp[i] %= MOD; } } System.out.println(dp[n]); } }
import java.util.Scanner; public class Main { public int howManyTrees(int n) { if (n < 1) return 0; else if (n == 1) return 1; else if (n == 2) return 2; else { int mod = (int) 1e9 + 7; long[] num = new long[n + 1]; num[0] = 1; num[1] = 1; for (int i = 2; i < n + 1; i++) { num[i] = 0; for (int j = 0; j < i; j++) { num[i] = num[i] + (num[j] * num[i - 1 - j]) % mod; num[i] %= mod; } } return (int)num[n]; } } public static void main(String[] args) { Main main = new Main(); Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); System.out.println(main.howManyTrees(n)); } }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main(int argc, char** argv){ int n; while(cin >> n){ vector<long long> temp(n+1, 0); temp[0] = 1; temp[1] = 1; temp[2] = 2; for(int i = 3; i <= n; i++){ for(int j = 0; j < i; j++){ // cout << j << " " << i-j-1 << endl; temp[i] += temp[j] * temp[i - j - 1]; temp[i] = temp[i] % (1000000007); } } cout << temp[n] << endl; } return 0; }