LC 1269. 停在原地的方案数

题目描述

这是 LeetCode 上的 1269. 停在原地的方案数 ，难度为 困难。

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

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：steps = 3, arrLen = 2

输出：4

解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

示例 2：
1
2
3
4
5
6
7
输入：steps = 2, arrLen = 4

输出：2

解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动

示例 3：
1
2
3
输入：steps = 4, arrLen = 2

输出：8

提示：

  • 1 <= steps <= 500
  • 1 <= arrLen <= $10^6$

动态规划

这道题的可变维度分析不算复杂，因此这次就不从 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$ 的范围。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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) 并打开注释，可以看到少计算了多少「无效状态」。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]$，使用「滚动数组」方式进行优化即可。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1269 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。