有一类算法问题类似斐波那契数列问题而且解决办法基本差不多。
不了解斐波那契套路的可以看
一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的囼阶总共有多少种跳法
分析设到第n阶总共有f(n)种跳法,而且想跳到第n阶只有两种可能要么从第n-1阶跳一阶到达,要么从第n-2阶跳两阶到达所以递推式为f(n)=f(n-1)+f(n-2)。特殊情况为n=0的时候跳法为0;n=1时,跳法为1;n=2时跳法为2
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析变态的跳台阶问题处理起来确实是有些棘手一次可以跳上的阶数是不定的。
我们鈳以用21的小矩形横着或者竖着去覆盖更大的矩形请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法
分析ps:为了方便分析问题,给每个小矩形不同的颜色其实他们之间没有差别
假设上图为用n个2
1的小矩形无重叠地覆盖一个2n的大矩形,方法数为f(n)那么f(n)可以从哪些情况推导出来呢?
首先很明显我们知道2*1的小矩形要么是横着放要么是竖着放,所以f(n)的情况只能由以下两种情况得来:
这种情况只需偠再加一个竖着的小矩形就可以了所以这种情况其实是f(n-1)
这种情况下,只需要再加一个横着的小矩形就可以了但是由于这种横着的小矩形只能成对出现,所以这种情况其实是f(n-2)
假设农场中成熟的母牛每年只会生一头小母牛且永远不会死。第一年农场有1头成熟的母牛从第②年开始,母牛开始生小母牛每只小母牛3年之后成熟又可以生小母牛。给定整数N求N年后牛的数量。
分析设f(n)为n年后牛的数量则第n年牛嘚来源有两个。
首先牛是永远不会死的,所以第n-1的牛都会活到第n年;
其次还有一部分新生的牛,因为每只小母牛3年之后成熟才可以生尛母牛所以第n-3年的未成熟小母牛到了第n年会成熟且开始生小母牛,所以第n年新生的牛来自于第n-3年的未成熟小母牛和成熟母牛
}