【动态规划】LeetCode96.不同的二叉搜索树

96. 不同的二叉搜索树

给定一个整数 n&＃xff0c;求以 1 … n 为节点组成的二叉搜索树有多少种&＃xff1f;

示例:

输入: 3
输出: 5
解释:
给定 n &＃61; 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1\ / / / \ \3 2 1 1 3 2/ / \ \2 1 2 3

解题思路

class Solution_96 {public int numTrees(int n) {int[] dp &＃61; new int[n &＃43; 1];dp[0] &＃61; 1;dp[1] &＃61; 1;for (int i &＃61; 2; i < n &＃43; 1; i&＃43;&＃43;) {for (int j &＃61; 1; j < i &＃43; 1; j&＃43;&＃43;) {dp[i] &＃43;&＃61; dp[j - 1] * dp[i - j];}}return dp[n];}
}