爬楼梯问题（DP、DFS、排列组合、递归）

╰半橙微兮° 2023-06-19 12:30 28阅读 0赞

## **问题描述** ##

假设你现在正在爬楼梯，楼梯有 n 级。每次你只能爬 1级或者 2级，那么你有多少种方法爬到楼梯的顶部？

我们规定刚开始在第0层。

下面介绍4种方法：

## 1.动态规划 ##

dp\[n\]：表示到达第n层台阶有dp\[n\]种方法  
转移方程：dp\[n\]=dp\[n-1\]+dp\[n-2\] (n>2); 其中dp\[1\]=1,dp\[2\]=2;  
简单分析：假设我们要走到第n层台阶，他的最后一步有两种决策，一个是走一步，另一个是走两步，所以到达第n层的方法=到达第n-1层的方法+到达第n-2层的方法。

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll dp[50],n,ans;
    void init()      //dp
    { 
     	dp[1]=1,dp[2]=2;
     	for(int i=3;i<=40;i++)
      	    dp[i]=dp[i-1]+dp[i-2];
    }
    int main()
    { 
        init();
        cin>>n;
        cout<<dp[n]<<endl;
     return 0;
    }

## 2.DFS ##

深度优先搜索：一直暴力搜索到第n层台阶。

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll n,ans;
    void dfs(int step)
    { 
    	if(step==n)
    	{ 
    		ans++;
    		return;
    	}
    	if(step>n)
    		return;
    	for(int i=1;i<=2;i++)
    	{ 
    		dfs(step+i);
    	}
    } 
    int main()
    { 
    	cin>>n;
    	dfs(0);
    	cout<<(ll)ans<<endl;
    	return 0;
    }

DFS还可以输出走过的路径

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    ll dp[50],n,ans,number;
    ll m[maxn];
    void dfs(int step,int s)
    { 
    	if(step==n)
    	{ 
    		for(int i=0;i<s;i++)
    		{ 
    			cout<<m[i];
    			if(i!=s-1)
    				cout<<"-";
    			else
    				cout<<endl;
    		}
    		return;
    	}
    	if(step>n)
    		return;
    	for(int i=1;i<=2;i++)
    	{ 
    		m[s]=i;
    		dfs(step+i,s+1);
    		m[s]=0;
    	}
    } 
    int main()
    { 
    	int t;
    	cin>>t;
    	while(t--)
    	{ 
    		cin>>n;
    		dfs(0,0);
    	}
    	return 0;
    }

## 3.排列组合 ##

我们假设到达第n层台阶需要走i个2步，那么走1步的就有（n-2 \* i）个，一共需要走n-i步。我们需要计算C（i，n-i） i属于\[0,n/2\] ，计算时我们计算的是\[1,n/2\]，因为计算组合数i做分母，只需要在最后的结果+1就行。  
组合数C（i，n-i）的计算公式为: ( n-i )! / ( i! \* (n-i-i)! ) 经历过高考的人都会这个公式。  
下面才是重点，如果暴力计算组合数数据会溢出的，N！阶乘数太大了。

优化组合数：C（m，n）= n! / ( m! \* (n-m)!)  
我们先做一个约分，约分 n! / m! =(m+1) \* (m+2) \* ··· \*(n-1) \* n  
为啥我们除以m！ ，这里我们就认为m！比（n-m）！大，如果（n-m）！> m! ，交换两个数的值。方便计算。  
这样一般的数据范围数据不会溢出，如果数据范围很大的话，运用卢卡斯定理，请自行百度，这个不是重点。  
组合数计算代码：

ll C(ll m,ll n)
    { 
    	if(m<n-m) m=n-m;
    	for(int i=n;i>=m+1;i--)
    		ans*=i;
    	for(int i=1;i<=n-m;i++)
    		ans/=i;
    	return ans;	
    }

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll number;
    ll solve(ll n)
    { 
    	ll num=n/2,count;
    	for(ll i=1;i<=num;i++)
    	{ 
    		ll p=i,q=n-i;
    		if(p<q-p) p=q-p; 
    		count=1;
    		for(int j=p+1;j<=q;j++)
    			count*=j;
    		for(int k=1;k<=q-p;k++)
    			count/=k;
    		number+=count;
    	}
    	return number+1;
    }
    int main()
    { 
    	ll n;
    	cin>>n;
    	number=0;
    	if(n==1)
    		cout<<"0"<<endl;
    	else
    		cout<<(ll)solve(n)<<endl;
    	return 0;
    }

## 4.递归 ##

递归：自己调用自己，到达临界点就返回值。

#include<iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    ll solve(ll n)
    { 
    	if(n==1||n==2)
    		return n;
    	return solve(n-1)+solve(n-2);
    }
    int main()
    { 
    	ll n;
    	cin>>n;
    	cout<<solve(n)<<endl;
    	return 0;
    }