三水做网站,青浦网站制作,网站 什么语言开发的,宁夏建设工程质量安全监督总网站Problem: 二叉树 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们可以定义dp[i][j]为节点个数为i且树的高度不超过j的二叉树的数量。我们可以通过枚举左子树和右子树的节点数量#xff0c;来计算dp[i][j]的值。具体来说#xff0c;对于每一个节点数量… Problem: 二叉树 文章目录 思路解题方法复杂度Code 思路 这是一个典型的动态规划问题。我们可以定义dp[i][j]为节点个数为i且树的高度不超过j的二叉树的数量。我们可以通过枚举左子树和右子树的节点数量来计算dp[i][j]的值。具体来说对于每一个节点数量k我们可以将其分配给左子树和右子树然后计算出所有可能的组合数量。这样我们就可以得到dp[i][j]的值。 解题方法 我们首先初始化dp[0][j]为1表示没有节点的二叉树只有一种可能。然后我们从i1开始对每一个节点数量i我们枚举所有可能的左子树和右子树的节点数量k。对于每一个k我们计算出左子树和右子树的二叉树数量然后将它们相乘得到所有可能的组合数量。我们将这些组合数量累加起来就得到了dp[i][j]的值。最后我们输出dp[n][m]即节点个数为n且树的高度不超过m的二叉树的数量。 复杂度
时间复杂度: 这个算法的时间复杂度是 O ( n 2 ∗ m ) O(n^2 * m) O(n2∗m)因为我们需要对每一个节点数量i和每一个高度j都枚举所有可能的左子树和右子树的节点数量k。 空间复杂度: 这个算法的空间复杂度是 O ( n ∗ m ) O(n * m) O(n∗m)因为我们需要一个二维数组dp来存储所有的状态。 Code
import java.util.*;
import java.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int MAXN 51;static int MAXM 51;static int n, m;static int MOD 1000000007;static long[][] dp new long[MAXN][MAXN];public static void main(String[] args) throws IOException {n nextInt();m nextInt();for(int j 0; j m; j) {dp[0][j] 1;}for(int i 1; i n; i) {for(int j 1; j m; j) {dp[i][j] 0;for(int k 0; k i; k) {dp[i][j] (dp[i][j] dp[k][j - 1] * dp[i - k - 1][j - 1] % MOD) % MOD;}}}out.println(dp[n][m]);out.flush();}static int nextInt() throws IOException {sr.nextToken();return (int)sr.nval;}
}
