首页 > 试题广场 >

机器人达到指定位置方法数

[编程题]机器人达到指定位置方法数

热度指数：7768 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模。

输入描述:

输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。

输出描述:

输出一个整数，代表最终走到P的方法数对取模后的值。

示例1

输入

5 2 3 3

输出

说明

1).2->1,1->2,2->3

2).2->3,3->2,2->3

3).2->3,3->4,4->3

示例2

输入

1000 1 1000 1

输出

591137401

说明

注意答案要取模

备注:

时间复杂度,空间复杂度。

算法知识视频讲解

Python

独坐海风秋

只过25%。。。也不知道为啥，以及这个平台上写python的真的好少啊

n,m,k,p = map(int,input().split())
if n < 2&nbs***bsp;k < 1&nbs***bsp;m < 1&nbs***bsp;m > n&nbs***bsp;p < 1&nbs***bsp;p > n:
    print(0)
dp = [0] * (n+1)
dp[p-1] = 1

for i in range(k):
    leftup = dp[0]
    for j in range(n):
        temp = dp[j]
        if j == 0:
            dp[j] = dp[j+1]%100000007
        elif j == n-1:
            dp[j] = leftup%100000007
        else:
            dp[j] = (leftup + dp[j+1])%100000007
        leftup = temp
print(dp[m-1])

发表于 2020-08-08 15:50:41 回复(0)