C++递推经典案例No.1——青蛙跳台问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
这是一个经典的递归/动态规划的例题，代码部分并不难，关键是要理清思路。由于每次可以跳1个或者两个，所以跳到当前台阶的来源只有两种：下一个和下两个台阶。因此，来到当前台阶的方案数，其实是前两者方案数的和！以此类推，直到找到最下面两个台阶（0和1）即可解出答案。
此处，我们用二叉树的思想进行简单的理解：
如上图，直到找到0或1，才能达到本次递归的终点（0or1都对）。
具体代码如下：
#include
#include
using namespace std;int main(int argc, char** argv)
{int n=0;cin>>n;vector V;V.push_back(1);V.push_back(1);//压入0和1对应的方案数作为递归终点 for(int i=2;i<=n;i++){int temp=V[i-1]+V[i-2];//方案数等于前两项的和 V.push_back(temp);}cout< 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！