本文介绍: dp[j]为j为头结点左子树节点数量,dp[i – j-1]为以j为头结点右子树节点数量。dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量。元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量。元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量。元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量。
算法:
看到这道题的时候有点懵,可以举几个例子,找规律
动规五部曲:
1.确定dp数组及下标
2.确定递推公式
3.递推初始化
4.确定遍历顺序
5.举例推导dp数组
正确代码:
注意:
时间空间复杂度:
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。