题目描述

描述转载自力扣《1269. 停在原地的方案数》

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

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

给你两个整数 stepsarrLen ,请你计算并返回:在恰好执行 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

解题思路

  1. 这道题是动态规划题。有个做动态规划题的规律:有多少传参,决定了动态规划数组的维度(不过事后可以降维)。题目有两个参数,步数 steps 和 数组长度 arrLen,我们可以创建一个二维数组 dp,则 dp[i][j] 表示第 i 步后停在索引 j 的方案数;
  2. 因为每步可以进行“向左,向右,不动”三种操作,所以我们就确定了状态转移方程
    图片说明
  3. 初始状态 dp[0][0] = 1;
  4. 因为步数 steps 可能比数组长度 arrLen 还要小,所以 dp 的列长度为
    图片说明
    又因为题目要求结尾停在索引 0 处,走太远是回不到 0 的,所以 dp 的列长度为
    图片说明

Java 代码实现

  1. 二维数组
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int colLen = Math.min(steps + 1, arrLen);
        int[][] dp = new int[steps + 1][colLen];
        dp[0][0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            for (int j = 0; j < colLen; ++j) {
                dp[i][j] = dp[i - 1][j] % mod;
                if (j != colLen - 1) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % mod;
                if (j != 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
            }
        }
        return dp[steps][0];
    }
}
  1. 一维数组
class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int colLen = Math.min(steps/2 + 1, arrLen);
        int[] dp = new int[colLen];
        dp[0] = 1;
        for (int i = 1; i < steps + 1; ++i) {
            int[] temp = new int[colLen];
            for (int j = 0; j < colLen; ++j) {
                temp[j] = dp[j];
                if (j != colLen - 1) temp[j] = (temp[j] + dp[j + 1]) % mod;
                if (j != 0) temp[j] = (temp[j] + dp[j - 1]) % mod;
            }
            dp = temp;
        }
        return dp[0];
    }
}