王道出现的动态规划

1.n个不同的结点构造的BST树形态个数

2025王道P305

image-20240930193251945

void slove(){
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 1;i<=20;i++){
        // i代表者总结点个数
        // 将i+1个节点划分成左右子树 1 + i
        for(int j = 0;j<=i;j++){
            dp[i+1] += dp[j]*dp[i-j];   
        }
    }
}
/*
1 2 3 4 5 6 7 8 9 10 
1 2 5 14 42 132 429 1430 4862 16796 
*/

2.高度为n的AVL树的形态个数

2025王道P305

image-20240930193251945

void slove(){
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2;i<20;i++){
        // 假设共有i层
        dp[i] = dp[i-1]*dp[i-2]*2 + dp[i-1] * dp[i-1];
    }
}

/*
1 2 3 4 5 6 7 8 9 10 
1 3 15 315 108675
*/

3.含有n层结点的AVL树至少有多少结点

2025王道P305

image-20240930193251945

void slove(){
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2;i<20;i++){
        // 假设共有i层
        dp[i] = dp[i-1] + dp[i-2] + 1;
    }
}
/*
1 2 3 4 5 6 7 8 9 10 
1 2 4 7 12 20 33 54 88 143 
*/

4.给定n个节点,用快速排序,求最少的比较次数

2025王道P360

image-20240930193251945