一、题目

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

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

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

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

点击查看原题

二、思路

不管什么题目，优先考虑暴力法进行求解，暴力法很简单，使用回溯法，每次都有三个选择，那就是向左、向右、不动，只有终点在0处才计入有效路径中。但可想而知，该方法造成的时间复杂度极高，需要使用记忆化来减少重复遍历的情况。

1）动态规划

用dp数组，其中dp[i][j]代表第i步操作到达j位置的路径数量。结合题意的三种选择方式，可以得到如下的状态转移方程：

其中

dp[i-1][j-1]项：就是代表在j-1位置向右走一步，到达j位置 dp[i-1][j-1]项：就是代表在j位置停留 dp[i-1][j+1]项：就是代表在j+1位置向左走一步，到达j位置

由于考虑到边界条件，可以在dp数组的两侧增加两列，避免j-1和j+1时越界。那么，初始化就需要设定为dp[0][1]=0（由于增加一列，原来的位置0变为了位置1）

2）优化空间复杂度

通过状态转移方程可以看出第i步的状态只依赖于第i-1步的状态，那么可以使用两个状态数组进行计算newDp、oldDp，oldDp[j]为上一步的到达位置j的路径数量，newDp[j]为这一步到达位置j的路径数量，那么有状态转移公式为：

三、代码

1)动态规划

class Solution {
    public int numWays(int steps, int arrLen) {
        if (arrLen == 1) {
            return 1;
        }
        // 在能回到原点的情况下，能到达的最右侧为steps/2 + 1
        // 所以设定dp的列宽为arrLen和steps/2 + 1的最小值
        int len = Math.min(steps/2 + 1, arrLen);
        // 使用long防止加法溢出
        long[][] dp = new long[steps+1][len + 2];
        // long[][] dp = new long[steps+1][step + 2];    // 使用这种初始化会多占用一半的时间
        dp[0][1] = 1;
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length - 1; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i-1][j+1] + dp[i-1][j-1])%1000000007; 
            }
        }
        return (int)dp[steps][1];
    }
}

时间复杂度为O(stepsdp[0].length)，空间复杂度为O((steps+1) min(steps/2 + 1, arrLen))。

2）优化空间复杂度

class Solution {
    public int numWays(int steps, int arrLen) {
        if (arrLen == 1) {
            return 1;
        }
        int len = Math.min(steps/2 + 1, arrLen);
        long[] oldDp = new long[len + 2];
        long[] newDp = new long[len + 2];
        oldDp[1] = 1;
        for (int i = 1; i < steps+1; i++) {
            for (int j = 1; j < newDp.length - 1; j++) {
                newDp[j] = (oldDp[j] + oldDp[j+1] + oldDp[j-1])%1000000007; 
            }
            long[] t = oldDp;
            oldDp = newDp;
            newDp = t;
        }
        return (int)oldDp[1];
    }
}

时间复杂度不变，空间复杂度降低为O(2 * min(steps/2 + 1, arrLen))。