Python教程

动态规划算法练习——6、不同的二叉搜索树(python和C++描述)

本文主要是介绍动态规划算法练习——6、不同的二叉搜索树(python和C++描述),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

来源:代码随想录
本题的力扣链接:https://leetcode-cn.com/problems/unique-binary-search-trees/

目录

  • 1、题目描述:
  • 2、思路:
  • 3、代码:
    • 3.1 python代码:
    • 3.2 C++代码:
  • 4、总结:

1、题目描述:

在这里插入图片描述

2、思路:

太菜,只能把官方的思路拿过来了。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3、代码:

3.1 python代码:

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n+1)]
        dp[0], dp[1] = 1, 1 # dp数组边界初始化
        
        for i in range(2, n+1): # 遍历到的i作为根节点
            for j in range(1, i+1): # 以i为根节点,求左右子树可构建的种类
                dp[i] += dp[j-1] * dp[i-j] # 递推公式
        
        return dp[n]

在这里插入图片描述

3.2 C++代码:

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] = 1; dp[1] = 1; // dp数组边界初始化

        for(int i = 2; i <= n; i++){ // 这个遍历,就是以i为根节点
            for(int j = 1; j <= i; j++){ // 然后求i的左右子树能构建二叉搜索树的个数
                dp[i] += dp[j-1] * dp[i-j]; // 递推公式
            }
        }
    
    return dp[n];
    }
};

在这里插入图片描述

4、总结:

二叉搜索树就是:左子树比父节点小,右子树比父节点大。然后在构造二叉搜索树的时候,遍历这些节点,每次遍历时把当前的节点作为根节点,那么左子树和右子树依然按这样的方式构造。因此,可知原问题能分解成两个规模较小的子问题,且子问题可以复用,即,子问题的解能推导出总问题的解。所以,可以使用动态规划的方法求解此问题。

这篇关于动态规划算法练习——6、不同的二叉搜索树(python和C++描述)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!