【算法】斐波那契数列vs卡塔兰数列DP

1. 斐波那契数列

公式：

应用：爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution:def climbStairs(self, n):if n <= 1:return 1res = [0 for i in range(n+1)]res[0] = 1 #0层楼梯不用爬,1种res[1] = 1for i in range(2, n+1):res[i] = res[i-1] + res[i-2]return res[-1]

2. 卡塔兰数

公式：

应用：不同二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

二叉搜索树，左子树节点小于根，右子树节点大于根。递归求解：

res[i]表示有i个节点时，树的种类数。初始化res[i] = 0。

n == 0时，只有一种树，res[0] = 1

n == 1时，当以1为根时，左子树种类数res[0], 右子树种类数res[0], 则res[1] = res[0]*res[0]

n== 2 时，当以1为根时，左子树种类数res[0], 右子树种类数res[1], 则res[2] += res[0]*res[1]

                  当以2为根时，左子树种类数res[1], 右子树种类数res[0]，则res[2] += res[1]*res[0]

以此类推。。。

class Solution:def numTrees(self, n):""":type n: int:rtype: int"""#res[i] 指i个数时，二叉搜索树个数res = [0 for i in range(n+1)]res[0] = 1 #n为0时，个数为1for i in range(1, n+1):#当n为i时，树的个数为以1~i每个数为根时左子树*右子树for j in range(1,i+1):res[i] += res[j-1]*res[i-j]return res[-1]

应用：不同的二叉搜索树II

class Solution:def generateTrees(self, n):""":type n: int:rtype: List[TreeNode]"""if n < 1:return []return self.generate( 1, n)def generate(self,start,end):res = []if start > end:res.append(None)return resfor i in range(start, end+1):left = self.generate(start, i-1)right = self.generate(i+1,end)for l in left:for r in right:root = TreeNode(i)root.left = lroot.right = rres.append(root)return res

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！