爬楼梯问题（DP、DFS、排列组合、递归）大灯清洗装置
问题描述
假设你现在正在爬楼梯，楼梯有 n 级。每次你只能爬 1级或者 2级，那么你有多少种⽅法爬到楼梯的顶部？
我们规定刚开始在第0层。
下⾯介绍4种⽅法：
1.动态规划
转移⽅程：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;
return0;
}
2.DFS人脸识别医疗
深度优先搜索：⼀直暴⼒搜索到第n层台阶。
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;
手机防盗系统return0;
}
DFS还可以输出⾛过的路径
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);
}
return0;
}
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;
return0;
}
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;
return0;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议