假设我们在n个长度列表的位置0，并且在每一步上，我们可以向右移动一个位置或向左移动一个位置（不超出范围），或停留在同一位置。现在，如果我们可以精确地走k步，那么我们就必须找出可以走多少个唯一的步数并返回到索引0。如果答案很大，则返回mod 10 ^ 9 + 7。
因此，如果输入类似n = 7 k = 4，则输出将为9，因为操作是-
[右，右，左，左]，
[右，左，右，左]，
[住宿，住宿，住宿，住宿]，
[右，左，停留，停留]，
[Stay，Stay，Right，Left]，
[右，留，留，左]，
[右，留，左，留]，
[停留，右，左，停留]，
[停留，向右，停留，向左]，
为了解决这个问题，我们将遵循以下步骤-
m：= 10 ^ 9 + 7
N：=长度
定义一个功能dp()。我要跳
如果跳跃等于0，则
返回（当我等于0时为true，否则为false）
计数：= dp（i，跳-1）
如果我> = 0，那么
计数：=计数+ dp（i + 1，跳-1）
如果我<= N-1，则
计数：=计数+ dp（i-1，跳-1）
返回计数
从主要方法执行以下操作：
返回dp(0,n)mod m
让我们看下面的实现以更好地理解-
class Solution: def solve(self, length, n): MOD = 10 ** 9 + 7 N = length def dp(i, jumps): if jumps == 0: return +(i == 0) count = dp(i, jumps - 1) if i >= 0: count += dp(i + 1, jumps - 1) if i <= N - 1: count += dp(i - 1, jumps - 1) return count return dp(0, n) % MOD ob = Solution()n = 7 k = 4 print(ob.solve(n, k))
7, 4
输出结果
9