一、题目描述

题面

链接: LeetCode 1269. 停在原地的方案数.

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

二、解题思路

1、动态规划

令dp[i][j]表示到第i步在j位置上的情况数，dp[i][j]的情况可以从dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]转移过来，注意边界。

• dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]

因为判断分支会减慢速度，推荐这种写法：

for(int i=1;i<=steps;i++)
{
   
	dp[i][0]=(dp[i-1][0]+dp[i-1][1])%M;
	dp[i][arrLen-1]=(dp[i-1][arrLen-1]+dp[i-1][arrLen-2])%M;
	//将边界放在外层循环单独处理，而不是在内层循环用if判断处理。
	for(int j=arrLen-2;j>0;j--)
	{
   
		dp[i][j]=((dp[i-1][j]+dp[i-1][j-1])%M+dp[i-1][j+1])%M;
	}
}

2、时间常数优化

同时观察到，由于arrLen如果大于2·steps，那么大于2·steps的位置根本无法达到，所以可以缩小arrLen范围。

arrLen=min(arrLen,(steps>>1)+1);

因为1e9+7的三倍会大于int的范围，用long long会变慢，所以dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]，所以在前两项相加时可以先膜一下：

dp[i][j]=((dp[i-1][j]+dp[i-1][j-1])%M+dp[i-1][j+1])%M;

3、空间常数优化

注意到按steps分层时第i层只取决于第i-1层，可以用滚动数组优化：

for(int i=1;i<=steps;i++)
{
   
	dp[i&1][0]=(dp[~i&1][0]+dp[~i&1][1])%M;
	dp[i&1][arrLen-1]=(dp[~i&1][arrLen-1]+dp[~i&1][arrLen-2])%M;
	for(int j=arrLen-2;j>0;j--)
	{
   
		dp[i&1][j]=((dp[~i&1][j]+dp[~i&1][j-1])%M+dp[~i&1][j+1])%M;
	}
}

像这样用位运算进行滚动数组，而不用if分支判断，会更快。

三、完整代码

class Solution
{
   
public:
	int numWays(int steps, int arrLen)
	{
   
		int M=1e9+7;
		arrLen=min(arrLen,(steps>>1)+1);
		int dp[2][arrLen];
		for(int i=arrLen-1;i>0;i--)
		{
   
			dp[0][i]=0;
		}
		dp[0][0]=1;
		for(int i=1;i<=steps;i++)
		{
   
			dp[i&1][0]=(dp[~i&1][0]+dp[~i&1][1])%M;
			dp[i&1][arrLen-1]=(dp[~i&1][arrLen-1]+dp[~i&1][arrLen-2])%M;
			for(int j=arrLen-2;j>0;j--)
			{
   
				dp[i&1][j]=((dp[~i&1][j]+dp[~i&1][j-1])%M+dp[~i&1][j+1])%M;
			}
		}
		return dp[steps&1][0];
	}
};

四、提交记录

时间超过100%，空间超过97%的提交。

求个关注

走过路过给个关注吧，谢谢qwq。