跳台阶
题目 跳台阶
思路分析
对于任意一个台阶级数 都可以分为由它-1级走一步到达 由它-2级走两步到达
比如 七级台阶可以分成6级台阶走一步 5级台阶走两步 然后再递归处理6级和5级的情况
由此生成这样一棵递归搜索树
最小状态 2级台阶有两种走法（0走两次1步 和 0走一次两步） 1级台阶只有一种走法（0走一步）
递归的解法就这样出来了
然后也如上图所示
很多地方都做了没意义的重复操作
发现其实只需要算最左边的那条分支 可以得到6 5 4 3 的方法数 把它们记录下来的话 右边就不需要做那么多递归操作了
直接简化成了近logn的复杂度
这就是记忆化搜索 用一个数组 记录一下每个节点的答案 再遇到相同节点时 直接取即可
接下来还能怎么优化
可以发现我们得到答案只是归的时候得到 和递并没有关系
能否省略从上往下递的步骤 直接由下而上的推出答案
(先把一个一个小问题解决 再解决由他们状态得到的母问题）
再优化的话就是空间上了
发现其实每一个后状态只需要它的前面一个状态和前面两个状态 其他的其实没必要存下来
那么 就可以用滚动数组的思路
因为这里已经是一维了 那么就可以优化成0维 用两个变量交替滚动覆盖
这是一道dp的典型题 由递归优化到记忆化搜索优化到简单的dp(递推）再使用滚动数组优化
也不难发现 dp就是将递归的递过程优化掉 从下而上地分析出答案 在这个过程中 又利用了记忆化的方式 潜在地剪去了很多不必要的分支 （一直都在做 得出答案 又同时微妙的省去了不必要的操作 我想这就叫做动态规划吧 妙）
代码实现
递归
#include<bits/stdc++.h>
using namespace std;
int n;
int dfs(int x)
{
//1 2是不可再分的 所以直接返回
if(x==1)
return 1;
else if(x==2)
return 2;
//对于其他情况就可以一直拆解递归
else
return dfs(x-1)+dfs(x-2);
}
int main()
{
cin>>n;
int res=dfs(n);
cout<<res;
return 0;
}
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int mem[N];//新增记忆化数组
int n;
int dfs(int x)
{
//若已存过 就返回记录的结果
if(mem[x])
return mem[x];
int sum=0;
if(x==1)
sum = 1;
else if(x==2)
sum = 2;
else
sum=dfs(x-1)+dfs(x-2);
mem[x]=sum;
return sum;
}
int main()
{
cin>>n;
int res=dfs(n);
cout<<res;
return 0;
}
递推（dp）
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int dp[N];
int n;
int main()
{
cin>>n;
dp[1]=1,dp[2]=2;
//把dfs的归部分 状态转移 成这样的递推公式
for(int i=3;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
cout<<dp[n];
return 0;
}
滚动优化
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
int a,b,fn;
a=1,b=2;
for(int i=1;i<=n;i++)
{
if(i==n)
cout<<a;
fn=a+b;
a=b,b=fn;
}
return 0;
}
💬 评论