概述
题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：
分析可知：如果要上n阶台阶，拥有的可能方法数目是：
f(n)=f(n-1)+f(n-2)+f(n-3)+……f(1)+f(0);
于是从前往后计算出各个项的值就可以，在简单台阶问题中需要保留2个计算结果供后面的计算使用，这里需要保留每一项的计算结果，可以使用一个数组来保存dp[i]，但是进一步分析发现可知：
f(n)=f(n-1)+f(n-2)+f(n-3)+……f(1)+f(0);
f(n-1)=f(n-2)+f(n-3)+……f(1)+f(0);
即f(n)=2*f(n-1)；
于是只要保留1项结果就可以了，再分析初始值，
f(0)=1;
f(1)=1;
f(2)=2;……
于是f(n)=2^(n-1);
常识：一个整数除以2可以使用向右位移1位来实现，即2>>1=1;一个整数乘以2可以使用向左位移1位来实现，4<<1=8，于是本题中f(n)=2<<(n-2)，注意左移动-1并不等价于右移1，于是对n=0,n=1特殊考虑。
注意：答案不要溢出，虽然不用处理但是在面试时要考虑溢出的问题并说明。
最后
以上就是欢喜板凳为你收集整理的动态规划9：变态跳台问题的全部内容，希望文章能够帮你解决动态规划9：变态跳台问题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复