这次针对之前的记忆化递归算法,我们来一个加强版
还是那只青蛙,这次他可以跳的更多,他可以一次跳一级,也可以一次跳两级,也可以一次跳n级,问如果有n级台阶,他有几种跳法?
所以还是去想它的表达式
1级:f(1) = 1;
2级:f(2) = 2;
3级:f(3) = 4;
4级:f(4) = 8;
行了,找到规律了,新跳的级数的表达式为f(n) = f(n-1)+f(n-2)+f(n-3)+...+1;
所以立马写出对应的递归算法:
还是采用记忆化递归算法的方法,速度也很快
每天一个,提神健脑,明天见