演算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+演算法面試，所以，為了提高大家的演算法能力，這個公眾號后續每天帶大家做一道演算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做 不同的二叉搜索樹，我們先來看題面：
https://leetcode-cn.com/problems/unique-binary-search-trees/
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
題意
給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？
樣例
解題
遞回子問題
假設 n 個節點存在二叉排序樹的個數是 G (n)，令 f(i) 為以 i 為根的二叉搜索樹的個數，則
G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n),
f(i)=G(i?1)?G(n?i)
class Solution {
public int numTrees(int n) {
if (n == 0 || n == 1) return 1;
int res = 0;
for (int i = 1; i <= n; i++) {
res += numTrees(i - 1) * numTrees(n - i);
}
return res;
}
}
動態規劃
從dp[0],dp[1]開始逐漸向后擴大
public class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
好了，今天的文章就到這里，如果覺得有所識訓，請順手點個在看或者轉發吧，你們的支持是我最大的動力，
上期推文：
LeetCode50-80題匯總，速度收藏！
LeetCode刷題實戰81：搜索旋轉排序陣列 II
LeetCode刷題實戰82：洗掉排序鏈表中的重復元素 II
LeetCode刷題實戰83：洗掉排序鏈表中的重復元素
LeetCode刷題實戰84： 柱狀圖中最大的矩形
LeetCode刷題實戰85：最大矩形
LeetCode刷題實戰86：分隔鏈表
LeetCode刷題實戰87：擾亂字串
LeetCode刷題實戰88：合并兩個有序陣列
LeetCode刷題實戰89：格雷編碼
LeetCode刷題實戰90：子集 II
LeetCode刷題實戰91：解碼方法
LeetCode刷題實戰92：反轉鏈表 II
LeetCode刷題實戰93：復原IP地址
LeetCode刷題實戰94：二叉樹的中序遍歷
LeetCode刷題實戰95：不同的二叉搜索樹 II
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/219830.html
標籤：其他
上一篇：JS前端面試題（三）