当前位置：首页 > news >正文

【多维DP】【hard】力扣1269. 停在原地的方案数

news 来源：原创 2025/6/17 23:59:36

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

动态规划

class Solution {
public:int numWays(int steps, int arrLen) {int MOD = 1e9 + 7;vector<vector<long long>> dp(arrLen+1, vector<long long>(steps+1));dp[0][0] = 1;for(int j = 1; j <= steps; j++){for(int i = 0; i < arrLen; i++){if(i == 0){dp[i][j] = (dp[i][j-1] + dp[i+1][j-1]) % MOD;}else{dp[i][j] = (dp[i-1][j-1] + dp[i][j-1] + dp[i+1][j-1]) % MOD;}}}return dp[0][steps];}
};

最开始想到的办法是定义一个二维数组dp[i][j]，来表示在i的位置的时候，并且以及已经进行了j步，最后所能到达下标0的位置的方案数。最后我们能列出状态转移方程dp[i][j] = (dp[i-1][j-1] + dp[i][j-1] + dp[i+1][j-1]) % MOD，但是最后测试结果通过28/32，显示超出内存限制和时间限制。

优化

class Solution {
public:int numWays(int steps, int arrLen) {int MOD = 1e9 + 7;int maxLen = min(arrLen - 1, steps / 2);vector<long long> dp(maxLen + 1, 0);  vector<long long> prev(maxLen + 1, 0);  prev[0] = 1;  for (int j = 1; j <= steps; j++) { for (int i = 0; i <= maxLen; i++) {dp[i] = prev[i];  // 向右走不变if (i > 0) dp[i] = (dp[i] + prev[i - 1]) % MOD;  // 向左走if (i < maxLen) dp[i] = (dp[i] + prev[i + 1]) % MOD;  // 向右走}prev = dp;}return dp[0] % MOD;  }
};

由于状态j一直是由上一个状态j-1进行状态转移而来，那么可以定义一个新的一维数组来储存上一轮的j-1状态下的dp[i]是多少，于是我们可以使用滚动数组的方式将二维压缩成一维。并且由于题目要求最后要返回原点，于是我们可以压缩原本要遍历的arrLen长度压缩为min(arrLen - 1, steps / 2);。最后返回dp[0]即可。

相关文章：