电子商务网站建设报告,wordpress主题图片路径设置,分析凡客诚品失败的原因,app store下载正版数楼梯(加强版)
题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题.
题目描述:
1楼到2楼楼梯有n级台阶。小明每…数楼梯(加强版)
题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题.
题目描述:
1楼到2楼楼梯有n级台阶。小明每次可以爬一格、走两格或者跨三格。问最终有几种方案到二楼答案对998244353取模。
输入格式:
一行一个数n。
输出格式:
一行一个数表示方案数。
输入输出样例
输入 #1:
3
输出 #1:
4
输入 #2:
5
输出 #2:
13
提示说明: n≤1000 时间1000ms 空间256M (上楼梯时不能往回走) 如果觉得这道题太难可以前往P1255先做数楼梯简单版 https://www.luogu.com.cn/problem/P1255
思路: 1.暴力法 很容易看出来这是一道递归题我们可以用暴力递归来解决。
#includeiostream
using namespace std;
static const int mod998244353;
long long sum0;
int n;
long long fun(int x){if(xn)return 1;if(xn)return 0;long long s10,s20,s30;s1fun(x1)%mod;s2fun(x2)%mod;s3fun(x3)%mod;return (s1s2s3)%mod;
}
int main(){cinn;coutfun(0)endl; return 0;
}
但是这个份代码会超时非常慢所以要进行优化
2.递推法
我们用 f(x) 表示爬到第 x 级台阶的方案数考虑最后一步可能跨了一级台阶也可能跨了两级台阶所以我们可以列出如下式子 f(x)f(x−1)f(x−2) 它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解因为每次只能爬 1 级或 2 级所以 f(x) 只能从 f(x−1)和 f(x−2) 转移过来而这里要统计方案总数我们就需要对这两项的贡献求和。 以上是动态规划的转移方程下面我们来讨论边界条件。我们是从第 0 级开始爬的所以从第 0 级爬到第 0 级我们可以看作只有一种方案即 f(0)1从第 0 级到第 1 级也只有一种方案即爬一级f(1)1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下根据转移方程得到 f(2)2f(3)3f(4)5……我们把这些情况都枚举出来发现计算的结果是正确的。 我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)的实现但是由于这里的 f(x) 只和 f(x−1)) 与 f(x−2)有关所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。
#includeiostream
using namespace std;
static const int mod998244353;
void fun(int n){long long max[1001];int i0;max[0]1;max[1]2;max[2]4;for(int j3;jn;j)max[j](max[j-1]max[j-2]max[j-3])%mod;coutmax[n-1]endl;
}
int main(){int n;cinn;fun(n); return 0;
}
总结 对于这道题有些像斐波那契数列需要将递归进行优化才可以解决。
题目链接
数楼梯(加强版) - 洛谷https://www.luogu.com.cn/problem/U267577
