动态规划题目（二）——跳台阶

待我称王封你为后i 2022-08-06 01:08 179阅读 0赞

**动态规划题目（二）——跳台阶**

# 1. 题目描述 #

一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。  
  
求总共有多少总跳法，并分析算法的时间复杂度。

# 2. 递归方式 #

对于这个动态规划问题，我们一样分两步来想：

*  假如我们跳了1级，那么剩下的跳法就是f(n-1)；
 *  假如我们跳了2级，那么剩下的跳法就是f(n-2)；

这个时候我们就可以递归实现了，慢！我们还需要跳出递归的条件，这个也是必不可少的！

这个题目而言，跳出递归的条件是当n==1, 2的时候，我们返回1, 2。

为什么是1,2呢？因为当n=1时，只有一种跳法；当n=2时，有两种跳法。然后有了初始值，而且只有两种情况（要么跳1级，要么跳2级），原来这就是一个斐波那契数列问题！

代码如下：

#include<iostream>
    using namespace std; 
    
    int findSolution(int N)
    {
    	int result[3]={0, 1, 2};   //初始情况
    	
    	if(N<=2)
    		return result[N]; 
    
    	return findSolution(N-1)+findSolution(N-2);   //递归实现
    }
    
    int main()
    {
    	int N=20; 
    
    	int num=findSolution(N); 
    
    	cout<<num<<endl;
    
    	return 0; 
    }

# 3. 非递归方式 #

非递归方式也是一定要掌握的！

如果说这是一个斐波那契数列问题的话，那么非递归方式实现也就比较容易了~

如下：

#include<iostream>
    using namespace std; 
    
    int findSolution(int N)
    {
    	int Fab[3]={1,1}; 
    	if(N<2)
    		return 1; 
    
    	for(int i=2; i<=N; i++)
    	{
    		Fab[2]=Fab[0]+Fab[1];   //这里需要注意推算规则
    		Fab[0]=Fab[1]; 
    		Fab[1]=Fab[2]; 
    	}
    	return Fab[2]; 
    }
    
    int main()
    {
    	int N=20; 
    
    	int num=findSolution(N); 
    
    	cout<<num<<endl;
    
    	return 0; 
    }

需要指出的是，这道题目的非递归方式的推算规则比较好想，当时之前《动态规划（一）》篇中的就不是很好想，大家以后一定要注意不同题目的推算规则！

另外，如果能够跳3级，那么实现的思路是一样的，只需要把初始的几个值替换掉就可以了~