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

英文原文

You have a pointer at index 0 in an array of size arrLen. 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 steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

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

Example 2:

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

Example 3:

Input: steps = 4, arrLen = 2
Output: 8

 

Constraints:

• 1 <= steps <= 500
• 1 <= arrLen <= 106

中文题目

有一个长度为 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 <= 500
• 1 <= arrLen <= 106

通过代码

高赞题解

动态规划

这道题的可变维度分析不算复杂，因此这次就不从 DFS 开始给大家分析了。

定义 $f[i][j]$ 代表当前剩余操作数为 $i$，所在位置为 $j$ 的所有方案数。

起始位置为 $0$，操作次数为 $step$，即有初始化条件 $f[step][0] = 1$，$f[0][0]$ 则是我们的最终答案。

不失一般性的考虑 $f[i][j]$ 可以由哪些状态转移而来：

• 由「原地」操作到达当前状态，消耗一次操作，此时由状态 $f[i + 1][j]$ 转移而来
• 由「向左」操作到达当前状态，消耗一次操作，此时由状态 $f[i + 1][j + 1]$ 转移而来
• 由「向右」操作到达当前状态，消耗一次操作，此时由状态 $f[i + 1][j - 1]$ 转移而来

求的是方案数，即最终的 $f[i][j]$ 为三者累加值。

同时我们发现 $f[i][x]$ 依赖于 $f[i + 1][y]$，因此我们需要按照「$step$ 从大到小」的顺序进行转移。

同时我们根据「最终回到下标 $0$ 位置」可以推断出，最远到达的位置为 $step / 2$（再远就回不来了）。将最远到达位置与数组最大下标取 $min$ 即可确定维度 $step$ 的范围。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1]; 
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            for (int j = 0; j <= max; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}

• 时间复杂度：共有数量级为 $step * max$ 个的状态需要被转移。复杂度为 $O(step * max)$
• 空间复杂度：$O(step * max)$

---

优化

1. 对时间复杂度进行「常数级别的优化」

$f[0][0]$ 并不依赖于操作次数同为 $0$ 的其他位置的状态，而只依赖于操作次数为 $1$ 的特定位置的状态。同理其他状态也是。

因此我们会发现随着「可操作次数」的减少，「可达到的最远位置」下标也会逐步缩小。从目标状态 $f[0][0]$ 进行倒推的话，会发现「可达到的最远位置」等于「可操作次数」。

所以其实可以从两者取一个 $min$ 就能够有效减少「无效状态」的计算。数据量越大，这个性质带来的剪枝效果越好。

PS. 为了方便你看到优化前后的差别，我增加了打印注释，使用测试数据 (500, 100000) 并打开注释，可以看到少计算了多少「无效状态」。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[steps + 1][max + 1]; 
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            // if (edge != max) System.out.println(edge + " " + max);
            for (int j = 0; j <= edge; j++) {
                f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
                if (j - 1 >= 0) f[i][j] = (f[i][j] + f[i + 1][j - 1]) % mod;
                if (j + 1 <= max) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}

• 时间复杂度：共有数量级为 $step * max$ 个的状态需要被转移。复杂度为 $O(step * max)$
• 空间复杂度：$O(step * max)$

2. 对空间复杂度进行「维度级别的优化」

这个优化思维难度就要低很多了，利用 $f[i][x]$ 依赖于 $f[i + 1][y]$，使用「滚动数组」方式进行优化即可。

代码：

[]
class Solution {
    int mod = (int)1e9+7;
    public int numWays(int steps, int len) {
        int max = Math.min(steps / 2, len - 1);
        int[][] f = new int[2][max + 1]; 
        f[steps&1][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = Math.min(i, max);
            int a = i & 1, b = (i + 1) & 1;
            for (int j = 0; j <= edge; j++) {
                f[a][j] = 0;
                f[a][j] = (f[a][j] + f[b][j]) % mod;
                if (j - 1 >= 0) f[a][j] = (f[a][j] + f[b][j - 1]) % mod;
                if (j + 1 <= max) f[a][j] = (f[a][j] + f[b][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
}

• 时间复杂度：共有数量级为 $step * max$ 个的状态需要被转移。复杂度为 $O(step * max)$
• 空间复杂度：$O(max)$

统计信息

通过次数	提交次数	AC比率
30388	61891	49.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言