商汤2018.9.7笔试台阶问题

深碍√TFBOYSˉ_ 2022-05-14 12:43 204阅读 0赞

\#问题描述  
一层楼共有n级台阶，一次可以上至少1级但不超过m级台阶，求有多少种不同的上楼方案数。由于结果可能很大，你只需要输出结果对10007取模的值即可  
**输入：**  
一行，正整数n和m  
**输出：**  
一个整数，对10007取模的结果  
**样例输入1：**  
4 3  
**样例输出1：**  
7  
**样例输入2：**  
1024 5  
**样例输出2：**  
8590  
**提示：**  
先认为m总是等于n的，那么：  
当n=3时，有4种方案：  
![这里写图片描述][70]  
当n=4时，有8种方案：  
![这里写图片描述][70 1]  
当n=5时，有16种方案：  
![这里写图片描述][70 2]  
\#思路  
整体思路是斐波那契数列，但是和常见的爬楼梯问题不一样，常见爬楼梯问题是：每次只可以排1级台阶或者2级台阶，递推公式是F(n)=F(n-1)+F(n-2);F（1）=1，F（2 ）=2；其形式和斐波那契数列是一样的（递推公式后面是两项）。  
而此题是可以最多爬m级台阶（递归公式后面是m项）。

分析测试用例，n很大，得到的结果如果不取模就更大（大得多），但m很小。

按照提示，写出m=3,4,5，n=5情况下的方案数（注意这里不是递推，而是在提示里按照m大小数方案）：  
![这里写图片描述][70 3]  
观察上面方案数，发现如果再加个f(0)=1，使用递推式，f(n)=f(n-1)+f(n-2)+…+f(n-m)，就可以得到递推式了。  
![这里写图片描述][70 4]  
再以m=3为例，f(3)=f(0)+f(1)+f(2)，f(4)=f(1)+f(2)+f(3)，以此类推，验证了正确性。  
**需要注意：初始条件只有f(0)=1 f(1)=1 f(2)=2就够了，但是当m>=4的时候，递归式的后面有4项或者更多。比如当m=4时，计算f(3)时只能f(3) = f(0)+f(1)+f(2)，虽然都说了m=4所以递推式后面有4项但这里却只有3项用来计算，但f(3)前面只有3项啊，所以就把能加的加起来。**  
但这点在实际编程没有影响，因为出现这种情况，只是多加几个0.（详见滚动数组分析）

再来讲优化：  
1.存储数组大小：一般情况，数组大小需要是n+1大小的，但考虑到n可能很大，所以我们需要使用滚动数组，滚动数组大小m即可，以m=3为例（索引从0到2），  
![这里写图片描述][70 5]  
发现使用m大小的滚动数组即可。

2.存储结果取余：递推式是累加的过程。所以每累加一次，就取余%10007，和把最终结果%10007是一样的，但前者就可以避免存储过大的数。  
\#代码  
普通方法：没有上面两处优化。

n,m = map(int,input().split())
    re  = [0]*(n+1)
    re[0] = 1
    re[1] = 1
    re[2] = 2
    
    if n==1:
        print(1)
    elif n==2:
        if(m==1):
            print(1)
        else:
            print(2)
    else:
        for i in range(3,n+1):
            for j in range(i-1,i-m-1,-1):
                re[i] += re[j]
        print(re[n]%10007)

这种方法在遇到大的n时就会很慢，以1024 5作为输入为例，实际结果为：  
![这里写图片描述][70 6]  
而且还需要申请1024大小的数组。

优化版本：

n,m = map(int,input().split())
    re  = [0]*(m)#滚动数组，m个位置就够用
    re[0] = 1
    re[1] = 1
    re[2] = 2
    
    if n==1:
        print(1)
    elif n==2:
        if(m==1):
            print(1)
        else:
            print(2)
    else:
        for i in range(3,n+1):
            outer = i%m#指re中的索引
            for j in range(outer+1,outer+m):
                #递推式后面有m项，但内层循环只循环m-1次
                #因为是当前位置加上剩余的m-1项
                inner = j%m
                re[outer] = (re[outer] + re[inner])%10007
        print(re[n%m])

[70]: /images/20220514/7abb1de7ef84499ca3657414184e54e9.png
[70 1]: /images/20220514/829e17aae1d142a494e5cadd2bd9677b.png
[70 2]: /images/20220514/4dce466d33b04c83b792f049b49d5928.png
[70 3]: /images/20220514/37ce1c08f94348a8b18dba256230c97e.png
[70 4]: /images/20220514/f0be1a389d3e44fbbf15f7149ce97119.png
[70 5]: /images/20220514/d8c19220fb2c40aaa23d77c325aeb51b.png
[70 6]: /images/20220514/9c92b36800cd4d6299b660ef241250e2.png