【原】37岁，简历挂了一个月，面试机会都没有，后来简历改了一个数字，各种企业hr狂轰乱炸过来了。。

一网友说自己年龄37了，简历挂了一个月，面试机会都没有，后来把简历改了一个数字，就是把期望薪资从4万改成2万，然后各种企业hr狂轰乱炸过来了。

10年以上工作经验，如果是在一线城市的互联网大厂，月薪4万其实不算高。但毕竟37岁了，在想入职也很难。如果是在二三线城市，月薪4万已经很高了，很多公司是接不住的，降薪一半也不是不可以，既然有面试就先找吧，有合适的就先干着吧，来看下各位网友的精彩评论。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第96题：不同的二叉搜索树。也是字节和蔚来的一道面试题。

问题描述

来源：LeetCode第96题

难度：中等

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

示例1：

输入：n = 3

输出：5

示例2：

输入：n = 1

输出：1

• 1 <= n <= 19

问题分析

这题让计算 n 个节点可以构成多个二叉搜索树。我们可以这样来思考，二叉树肯定有根节点，去掉根节点之后还有 n-1 个子节点。在这 n-1 个子节点中，左子节点可以有 0 个，也可以有 1 个，也可以有 2 个……

如果左子节点是 j 个，那么右子节点就是 n-1-j 个，他们构成的二叉搜索树就是左子树构成的个数乘以右子树构成的个数，所以这是一个动态规划问题。

定义dp[i]表示 i 个节点构成的二叉搜索树个数，当 i 等于 1 的时候只有一种情况。当左子节点个数为 0 的时候，构成的二叉搜索树就是右子节点构成的个数，所以我们这里让dp[0]也等于 1 。

当计算 i 个节点的时候，我们只需要枚举左子树的个数从 0 到 i-1 即可，代码如下：

JAVA：

public int numTrees(int n) {
    int dp[] = new int[n + 1];
    dp[0] = dp[1] = 1;// 节点为0和1的时候，只有一种。
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            // j是左子节点个数，i-j-1是右子节点个数。
            dp[i] += dp[j] * dp[i - j - 1];
    return dp[n];
}

C++：

public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;// 节点为0和1的时候，只有一种。
        for (int i = 2; i <= n; i++)
            for (int j = 0; j < i; j++)
                // j是左子节点个数，i-j-1是右子节点个数。
                dp[i] += dp[j] * dp[i - j - 1];
        return dp[n];
    }

C：

int numTrees(int n) {
    int dp[20] = {0};
    dp[0] = dp[1] = 1;// 节点为0和1的时候，只有一种。
    for (int i = 2; i <= n; i++)
        for (int j = 0; j < i; j++)
            // j是左子节点个数，i-j-1是右子节点个数。
            dp[i] += dp[j] * dp[i - j - 1];
    return dp[n];
}

Python：

def numTrees(self, n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1  # 节点为0和1的时候，只有一种。
    for i in range(2, n + 1):
        for j in range(i):
            # j是左子节点个数，i-j-1是右子节点个数。
            dp[i] += dp[j] * dp[i - j - 1]
    return dp[n]

笔者简介

博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧