2020-12-11-天池-汇丰专场-个人赛-04-停在原地的方案数

待我称王封你为后i 2022-12-28 01:50 12阅读 0赞

[ link ][link]

## 停在原地的方案数 ##

###### 难度难度: ★☆☆☆ ######

### 题目描述 ###

--------------------

有一个长度为 arrLen的数组，开始有一个指针在索引 0处。
    每一步操作中，你可以将指针向左或向右移动 1步，或者停在原地（指针不能被移动到数组范围外）。
    给你两个整数 steps和arrLen ，请你计算并返回：在恰好执行 steps次操作以后，指针仍然指向索引 0处的方案数。
    由于答案可能会很大，请返回方案数 模 10^9+7 后的结果。

1<=steps<=15
    1<=allLen<=10^6

--------------------

### 示例 ###

样例 1：
    输入：
    3
    2
    输出：4
    说明：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
    向右，向左，不动
    不动，向右，向左
    向右，不动，向左
    不动，不动，不动
    
    样例 2：
    输入：
    2
    4
    输出：2
    说明：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
    向右，向左
    不动，不动
    
    样例 3：
    输入：
    4
    2
    输出：8

#coding=utf-8
    class Solution:
        """ @param steps: steps you can move @param arrLen: the length of the array @return: Number of Ways to Stay in the Same Place After Some Steps """
        def numWays(self, steps, arrLen):
            # write your code here
            A, mod = [0,1],10**9+7
            for x in range(steps):
                A[1:] = [sum(A[i-1:i+2]) % mod for i in range(1,min(arrLen+1,x+3))]
            return A[1] % mod

[link]: https://tianchi.aliyun.com/oj/186516216680835547/224425012525994809