题目描述
有一个长度为 arrLen
的数组,开始有一个指针在索引 0
处。
每一步操作中,你可以将指针向左或向右移动 1
步,或者停在原地(指针不能被移动到数组范围外)。
给你两个整数 steps
和 arrLen
,请你计算并返回:在恰好执行 steps
次操作以后,指针 恰好 指向索引 0
处的方案数。
由于答案可能会很大,请返回方案数 模 10^9 + 7
后的结果。
样例
输入:steps = 3, arrLen = 2
输出:4
解释:3 步后,总共有 4 种不同的方法可以停在索引 0 处。
向右,向左,不动
不动,向右,向左
向右,不动,向左
不动,不动,不动
输入:steps = 2, arrLen = 4
输出:2
解释:2 步后,总共有 2 种不同的方法可以停在索引 0 处。
向右,向左
不动,不动
输入:steps = 4, arrLen = 2
输出:8
限制
1 <= steps <= 500
1 <= arrLen <= 10^6
算法
(动态规划) $O(steps \min(steps, arrLen))$
- 状态 $f(i, j)$ 表示走了 $i$ 步,停留在位置 $j$ 的方案数。
- 初始时 $f(0, 0) = 1$。每次可以又三种转移,$f(i, j) = f(i - 1, j - 1) + f(i - 1, j) + f(i - 1, j + 1)$。位于 $0$ 和 $arrLen - 1$ 的位置只有两种转移。
- 最终答案为 $f(steps, 0)$。由于
steps
步最多走到steps
位置,所以数组长度最长为steps + 1
。
时间复杂度
- 状态数最多有 $O(steps \min(steps, arrLen))$ 个,每次转移的时间为常数,故总时间复杂度为 $O(steps \min(steps, arrLen))$。
空间复杂度
- 空间复杂度与状态数相同。
- 可以通过滚动数组来优化空间到 $O(\min(steps, arrLen))$。
C++ 代码
class Solution {
public:
int numWays(int steps, int arrLen) {
if (arrLen == 1)
return 1;
arrLen = min(arrLen, steps + 1);
vector<vector<int>> f(steps + 1, vector<int>(arrLen, 0));
const int MOD = 1000000007;
f[0][0] = 1;
for (int i = 1; i <= steps; i++) {
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
f[i][arrLen - 1] = (f[i - 1][arrLen - 2] + f[i - 1][arrLen - 1]) % MOD;
for (int j = 1; j < arrLen - 1; j++)
f[i][j] = ((f[i - 1][j - 1] + f[i - 1][j]) % MOD + f[i - 1][j + 1]) % MOD;
}
return f[steps][0];
}
};