number-of-ways-to-stay-in-the-same-place-after-some-steps

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have a pointer at index <code>0</code> in an array of size <code>arrLen</code>. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers <code>steps</code> and <code>arrLen</code>, return the number of ways such that your pointer is still at index <code>0</code> after exactly <code>steps</code> steps. Since the answer may be too large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
</pre>

Example 2:

<pre>
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
</pre>

Example 3:

<pre>
Input: steps = 4, arrLen = 2
Output: 8
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= steps &lt;= 500</code></li>
	<li><code>1 &lt;= arrLen &lt;= 106</code></li>
</ul>

numWays

Number of Ways to Stay in the Same Place After Some Steps

Number of Ways to Reach a Position After Exactly k Steps

number-of-ways-to-reach-a-position-after-exactly-k-steps

恰好移动 k 步到达某一位置的方法数目

Dynamic Programming

有一个长度为 <code>arrLen</code> 的数组，开始有一个指针在索引 <code>0</code> 处。

每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。

给你两个整数 <code>steps</code> 和 <code>arrLen</code> ，请你计算并返回：在恰好执行 <code>steps</code> 次操作以后，指针仍然指向索引 <code>0</code> 处的方案数。

由于答案可能会很大，请返回方案数 模 <code>10^9 + 7</code> 后的结果。

 

示例 1：

<pre>
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动
</pre>

示例  2：

<pre>
输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
</pre>

示例 3：

<pre>
输入：steps = 4, arrLen = 2
输出：8
</pre>

 

提示：

<ul>
	<li><code>1 <= steps <= 500</code></li>
	<li><code>1 <= arrLen <= 106</code></li>
</ul>