題目1

264. 醜數 II【中等】

題解

看完才發現，和之前做的這道一樣，只不過前一道是劍指offer裏的，這道是力扣自己的…詳細題解看鏈接裏那道就行

狀態定義：dp[i] 錶示第 i 個醜數

class Solution {
    
    public int nthUglyNumber(int n) {
    
        int[] dp=new int[n];
        dp[0]=1;
        int a=0,b=0,c=0;
        for(int i=1;i<n;i++){
    
            int n2=dp[a]*2,n3=dp[b]*3,n5=dp[c]*5;
            dp[i]=Math.min(n2,Math.min(n3,n5));
            if(dp[i]==n2)   a++;
            if(dp[i]==n3)   b++;
            if(dp[i]==n5)  c++;
        }
        return dp[n-1];
    }
}

時間複雜度：$O(n)$

空間複雜度：$O(n)$

題目2

96. 不同的二叉搜索樹【中等】

題解

動態規劃

首先複習一下二叉搜索樹的概念，

二叉查找樹（英語：Binary Search Tree），也稱為 二叉搜索樹、有序二叉樹（Ordered Binary Tree）或排序二叉樹（Sorted Binary Tree），是指一棵空樹或者具有下列性質的二叉樹：

1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 任意節點的左、右子樹也分別為二叉查找樹；
4. 沒有鍵值相等的節點。

接著，用動態規劃解這道題（不看題解真的不會啊嗚嗚），

綜合兩個公式可以得到卡特蘭數公式，G(n)即定義的狀態，求解這道題：
$G(n)=G(0)\ast G(n-1)+G(1)\ast G(n-2)+...+G(n-1)\ast G(0)$

class Solution {
    
    public int numTrees(int n) {
    
        int[] dp=new int[n+1];
        dp[0]=dp[1]=1;
        //i為根節點
        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];
    }
}

時間複雜度：$O(n^2)$

空間複雜度：$O(n)$

卡特蘭數

考研時候學的東西怕是都還給當時的自己了…

n個結點的二叉搜索樹的個數為卡特蘭數，直接套公式就出來了

class Solution {
    
    public int numTrees(int n) {
    
        long C=1;//用long防止計算過程中的溢出
        for(int i=1;i<n;i++){
    
            C=2*(2*i+1)*C/(i+2);
        }
        return (int)C;
    }
}

時間複雜度：$O(n)$

空間複雜度：$O(1)$