一文学会动态规划解题技巧

可以看到光是求f(6),就有两次重复的计算,f(4)求解了两次,f(3)求解了两次,时间复杂度是指数级别,递归时间复杂度怎么看,解决每个子问题需要的时间乘以子问题总数,每个子问题需要的时间即f(n)=f(n-1)+f(n-2)只做了一次加法运算,子问题的个数有多少呢,每个问题一分为二,是个二叉树,可以...

[洛谷日报第70期]NOIP2018初赛解析

第一层的节点数是k^0,接下来依次是k^1,k^2,k^3…k^{h-1},也就是说节点总数是\sum_{i=0}^{h-1}k^i,根据等比数列求和公式S_n=\frac{1-q^n}{1-q},可知答案为A。当然考场上以三叉树为例举例两三层也可以得到A。5.考虑累加,T_n=T_{n-1}+n=T_{n-2}+n-1+n=…....