首页 > 代码库 > 爬楼梯问题总结 (递推)

爬楼梯问题总结 (递推)

超级楼梯

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=2041

题意:

有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?

分析:

首先题目限制只能走一级或者两级, 所以逆向思考一下, 要到达n级楼梯, 只有两种方式,从(n-1)级 或 (n-2)级到达的。

所以可以用递推的思想去想这题,假设有一个数组s[n], 那么s[1] = 1(由于一开始就在第一级,只有一种方法), s[2] = 1(只能从s[1]上去 没有其他方法)。

那么就可以推出s[3] ~ s[n]了。

下面继续模拟一下, s[3] = s[1] + s[2], 因为只能从第一级跨两步, 或者第二级跨一步。

如果是第一级跨一步再跨一步, 就等于第二步跨一步,这就重复了。(因为每一级都是相差1, 所以不能有从哪一级跨出一步这种走法, 除了跨出一级就到达目的地)。

 

 

frog

链接:

http://acm.dhu.edu.cn/contest/view.html?id=873&index=2

题意:

这题可以说是上一题的加强版,可以看成有M级楼梯,刚开始你在0级(平地), 每次能跨L步,共有多少种走法。

分析:

这题可以类比上一题, 如果上一题只能走两步的话,走上n级考虑(n-1)和(n-2),那么这题可以看成走上n级考虑(n-1),(n-2)...(n-L)级。

那么同理 s[0] = 1; s[1] = 1;

然后s[2]~s[L]就可以推了(因为这一部分的前面都不足n级,特殊考虑)

for 2~L ← i

  s[i] = sum(s[0],s[i])

然后s[L+1]到s[n]的部分可以(这一部分前面肯定有n级, 一般情况)

for L+1 ~ n ← i

  s[i] = sum(s[i-1 - L],s[i-1])  //总长为L的楼梯的方法数之和

最后输出s[n]即可。

该题需要 % 1e9+7, 注意同余的特性:

(a+b) mod n = (a mod n + b mod n) mod n

(a-b) mod n = (a mod n - b mod n + n) mod n (因为a mod n 可能小于 b mod n  所以需要加上一个n)

#include<bits/stdc++.h>
using namespace std;
int n , l;
const int maxn = 100005;
const long long mod = 1e9 + 7;
long long dp[maxn];
int main()
{
    while(~scanf("%d %d", &n, &l))
    {
        if(l == 1)
        {
            printf("1\n");
            continue;
        }
        dp[0] = dp[1] = 1;
        int t = dp[0] + dp[1];
        for(int i = 2; i <= l; i ++)
        {
            dp[i] = t;
            t += dp[i];
            t %= mod;
        }
        for(int i = l+1; i <= n; i++)
        {
            dp[i] =((2*dp[i-1])%mod - (dp[i-1-l]%mod) + mod) % mod;
            //这部分可以推一下, 如 L = 2时,
            //     dp[4] = dp[3] + dp [2];
            //那么 dp[5] = dp[4] + dp[3] = dp[4] + dp[4] - dp[2] = 2*dp[4] - dp[2];
        }
        printf("%lld\n", dp[n]);
    }
}

 

爬楼梯问题总结 (递推)