[1269]. 停在原地的方案数

## [1269]. 停在原地的方案数

[原题链接](https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/)

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

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

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

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

**示例 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>

**提示：**

* `1 <= steps <= 500`
* `1 <= arrLen <= 10^6`

### 题解：

暴力解法，将每一步有可能走的可能都列出来，即向左走，向右走，不动，直接暴力解会超时，用记表方式记录算过的值，减少时间复杂度。由于数量级过大，取余规则为(a%b + c%b)%b =  (a+c)%b，防止数据溢出。

动态规划解法：
[力扣题解链接](https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/solution/ting-zai-yuan-di-de-fang-an-shu-by-leetcode-soluti/)

### 代码：

```cpp
class Solution {
long num_limit = pow(10,9) + 7; //最大数据现在 防止溢出
public:
 int helper(int steps,int arrLen, int cur_index,std::map<int,map<int,int>> &tmp)
 {
 if(tmp.count(cur_index) > 0 && tmp[cur_index].count(steps) > 0) 
 {
 return tmp[cur_index][steps];
 }

if(cur_index < 0 || cur_index >= arrLen) return 0; //越界
 if(steps == 0 && cur_index == 0)
 {
 return 1; //到达终点，该走法可行
 }
 if(steps <= 0) return 0; //步数用完未到终点，该方法不可行。

int left = helper(steps - 1,arrLen,cur_index + 1,tmp) % num_limit;  //往左走的情况
        int right = helper(steps - 1,arrLen,cur_index - 1,tmp) % num_limit; //往右走的情况
        int no_move = helper(steps - 1,arrLen,cur_index,tmp) % num_limit;   //原地不动的情况

int count = (((left + right) % num_limit) + no_move) % num_limit;
        tmp[cur_index][steps] = count;
        return count;

}
 int numWays(int steps, int arrLen) {
 std::map<int,map<int,int>> tmp; //映射关系<当前所在的点,<剩余步数，结果>> 减少重复计算
 int count = helper(steps,arrLen,0,tmp); 
 count %= num_limit; //结果取余防止溢出
 return count;
 }
};
```

```