LC 1269. 停在原地的方案数

题目描述

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

有一个长度为 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：

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$ 的范围。

Java 代码：

class Solution {
    public int numWays(int steps, int len) {
        int mod = (int)1e9+7, 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 + 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];
    }
}

C++ 代码：

class Solution {
public:
    int numWays(int steps, int len) {
        int mod = 1e9 + 7, maxv = min(steps / 2, len - 1);
        vector<vector<int>> f(steps + 1, vector<int>(maxv + 1, 0));
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            for (int j = 0; j <= maxv; 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 <= maxv) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
};

Python 代码：

class Solution:
    def numWays(self, steps: int, l: int) -> int:
        mod, maxv = 10**9 + 7, min(steps // 2, l - 1)
        f = [[0] * (maxv + 1) for _ in range(steps + 1)]
        f[steps][0] = 1
        for i in range(steps - 1, -1, -1):
            for j in range(maxv + 1):
                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 <= maxv: 
                    f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod
        return f[0][0]

TypeScript 代码：

function numWays(steps: number, len: number): number {
    let mod = 1e9 + 7, max = Math.min(Math.floor(steps / 2), len - 1);
    const f = Array.from({ length: steps + 1 }, () => Array(max + 1).fill(0));
    f[steps][0] = 1;
    for (let i = steps - 1; i >= 0; i--) {
        for (let j = 0; j <= max; 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 \times max$ 个的状态需要被转移。复杂度为 $O(step \times max)$
空间复杂度：$O(step \times max)$

优化

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

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

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

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

Java 代码：

class Solution {
    public int numWays(int steps, int len) {
        int mod = (int)1e9+7, 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);
            for (int j = 0; j <= edge; 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];
    }
}

C++ 代码：

class Solution {
public:
    int numWays(int steps, int len) {
        int mod = 1e9 + 7, maxv = min(steps / 2, len - 1);
        vector<vector<int>> f(steps + 1, vector<int>(maxv + 1, 0));
        f[steps][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = min(i, maxv);
            for (int j = 0; j <= edge; 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 <= maxv) f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
};

Python 代码：

class Solution:
    def numWays(self, steps: int, l: int) -> int:
        mod, maxv = 10**9 + 7, min(steps // 2, l - 1)
        f = [[0] * (maxv + 1) for _ in range(steps + 1)]
        f[steps][0] = 1
        for i in range(steps - 1, -1, -1):
            edge = min(i, maxv)
            for j in range(edge + 1):
                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 <= maxv: 
                    f[i][j] = (f[i][j] + f[i + 1][j + 1]) % mod
        return f[0][0]

TypeScript 代码：

function numWays(steps: number, len: number): number {
    let mod = 1e9 + 7, max = Math.min(Math.floor(steps / 2), len - 1);
    const f = Array.from({ length: steps + 1 }, () => Array(max + 1).fill(0));
    f[steps][0] = 1;
    for (let i = steps - 1; i >= 0; i--) {
        const edge = Math.min(i, max);
        for (let j = 0; j <= edge; 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 \times max$ 个的状态需要被转移。复杂度为 $O(step \times max)$
空间复杂度：$O(step \times max)$

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

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

Java 代码：

class Solution {
    public int numWays(int steps, int len) {
        int mod = (int)1e9+7, 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] = 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];
    }
}

C++ 代码：

class Solution {
public:
    int numWays(int steps, int len) {
        int mod = 1e9+7, maxv = min(steps / 2, len - 1);
        vector<vector<int>> f(2, vector<int>(maxv + 1, 0));
        f[steps & 1][0] = 1;
        for (int i = steps - 1; i >= 0; i--) {
            int edge = min(i, maxv);
            int a = i & 1, b = (i + 1) & 1;
            for (int j = 0; j <= edge; 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 <= maxv) f[a][j] = (f[a][j] + f[b][j + 1]) % mod;
            }
        }
        return f[0][0];
    }
};

Python 代码：

class Solution:
    def numWays(self, steps: int, l: int) -> int:
        mod, maxv = 10**9 + 7, min(steps // 2, l - 1)
        f = [[0] * (maxv + 1) for _ in range(2)]
        f[steps & 1][0] = 1
        for i in range(steps - 1, -1, -1):
            edge = min(i, maxv)
            a, b = i & 1, (i + 1) & 1
            for j in range(edge + 1):
                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 <= maxv: 
                    f[a][j] = (f[a][j] + f[b][j + 1]) % mod
        return f[0][0]

TypeScript 代码：

function numWays(steps: number, len: number): number {
    let mod = 1e9 + 7, max = Math.min(Math.floor(steps / 2), len - 1);
    const f = Array.from({ length: 2 }, () => Array(max + 1).fill(0));
    f[steps & 1][0] = 1;
    for (let i = steps - 1; i >= 0; i--) {
        const edge = Math.min(i, max);
        const a = i & 1, b = (i + 1) & 1;
        for (let j = 0; j <= edge; 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 \times max$ 个的状态需要被转移。复杂度为 $O(step \times max)$
空间复杂度：$O(max)$

最后

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

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

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

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

线性 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 45. 跳跃游戏 II 上一篇

LC 1310. 子数组异或查询下一篇