系列文章：

算法题目解析：从一道题目看动态规划

Leetcode 题目解析：274. H 指数

Leetcode 题目解析：279. 完全平方数

Leetcode 题目解析：287. 寻找重复数

Leetcode 题目解析：211. 添加与搜索单词 - 数据结构设计

Leetcode 题目解析：70. 爬楼梯

一 动态规划题目

本篇选择另一道题目来继续联系动态规划算法。leetcode 的第 96 题：96. 不同的二叉搜索树。

二 不同的二叉搜索树

2.1 题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

2.2 示例

输入：n = 3输出：5

三 解析

3.1 题目解析

给定一个整数 n，实际上就是固定了一个{1,2,3,...,n}的数组，希望用这些元素组成一个二叉搜索树，即要满足构成的树，根的左节点值总是小于根节点值，且右子树中的节点都大于根节点值。

为了构建出一棵二叉搜索树，我们可以从 1 到 n 遍历每个数字，在每一轮，把当前遍历的数字作为树的根节点值，1，⋯，i−1 作为左子树，将 i+1，⋯，n 作为右子树。如此我们也可以按照同样的方式递归构建左子树和右子树。因为这样构建的根节点值是不同的，所以得到的二叉树也是唯一的，不会与其他轮构建的二叉树重复。

通过这样的分析，每一轮的问题都可以分解成规模较小的两个子问题，且子问题的解可以复用，从而符合动态规划的条件。

3.2 解法思路

我们可以定义两个函数：（1） G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数；（2）F(i,n): 以 i 为根，数组长度为 n 的不同二叉搜索树个数(其中，1≤i≤n)；那么，G(n)就是题目的解。

不同的二叉搜索树的总数，是对遍历所有 i 的 F(i, n) 之和。也就是：

这个就是这道题目的状态转移方程；除此之外，我们还要确定边界条件（再敲黑板画重点：动态规划的两大要素）。当 n=0 时，是空数组，只能构建成空树，所以 G(0)=1；当 n=1 时，只有一个元素，构建的树就只能有一个根节点，G(1)=1；由此向下，可以得到：

3.3 代码实现

public int numTrees(int n) {    int[] G = new int[n + 1];    G[0] = 1;    G[1] = 1;
    for (int i = 2; i <= n; ++i) {        for (int j = 1; j <= i; ++j) {            G[i] += G[j - 1] * G[i - j];        }    }    return G[n];}