题目大意：
停在原地的方案数
有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。
每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。
给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。
由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。
示例 1：
输入：steps = 3, arrLen = 2 输出：4 解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。 向右，向左，不动 不动，向右，向左 向右，不动，向左 不动，不动，不动
示例 2：
输入：steps = 2, arrLen = 4 输出：2 解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。 向右，向左 不动，不动
示例 3：
输入：steps = 4, arrLen = 2 输出：8
提示：
1 <= steps <= 5001 <= arrLen <= 10^6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1269
解题思路分析：
这又是一道标准的DP题目，之前博客多次提到过，理论上动态规划题目都可以使用递归加记忆数组来代替。本人更热衷于递归，因此本题使用递归来解题。
对于当前点可移动的方案有以下三种情况：
- 若当前位置大于0，可以向左移动
- 若当前位置小于最后一位，可以向右移动
- 任何位置都可以原地不动
递归终止条件为当前index为0，并且剩余步数为0，此时步数方案加一。
还有一个终止条件是，当步数小于index时，由于所剩的步数无法支持返回起点，此时不存在返回起点的步数方案，返回0。这一点也可以得出另一个结论，不论数组长度为多长，要想最终返回起点，我们要保证足够的往返步数，因此，能够到达的最远index一定不能超过步数的一半。
我们可以定义一个memo记忆数组，int[][] memo，memo[i][j]代表，还剩下i步时，从下标j返回下标0的方案数。最终答案为memo[steps][0]。
实现代码：
int[][] memo; // 记忆数组
public int numWays(int steps, int arrLen) {
// 初始化记忆数组
// memo[i][j]代表，还剩下i步时，从下标j返回下标0的方案数
// 由于能够到达的最远index一定不能超过步数的一半，
// j的最大值为steps/2+1
memo=new int[steps+1][steps/2+1];
// 递归求解
return helper(steps, arrLen, 0);
}
int helper(int steps, int arrLen, int index){
// 如果剩余步数小于index，说明已无法返回起点，返回0
if(steps<index) return 0;
// 如果返回起点时刚好使用完步数，方案加一。
if(steps==0 && index==0) return 1;
// 如果记忆数组存在当前解，直接返回。
if(memo[steps][index]>0) return memo[steps][index];
long res=0; // 返回结果
// 当index大于0时，可以向左移动
if(index>0){
res=(res+helper(steps-1,arrLen,index-1))%1000000007;
}
// 当index小于数组末尾时，可以向右移动
if(index<arrLen-1){
res=(res+helper(steps-1,arrLen,index+1))%1000000007;
}
// 任何位置都可以原地不动
res=(res+helper(steps-1,arrLen,index))%1000000007;
// 结果存入记忆数组
memo[steps][index]=(int)res;
return (int)res;
} 本题解法执行时间为4ms。
Runtime: 4 ms, faster than 100.00% of Java online submissions forNumber of Ways to Stay in the Same Place After Some Steps.
Memory Usage: 35.5 MB, less than 100.00% of Java online submissions for Number of Ways to Stay in the Same Place After Some Steps.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1269-number-of-ways-to-stay-in-the-same-place-after-some-steps-解题思路分析/