2021/5/13 停在原地的方案数

题目描述

描述转载自力扣《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

输入：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];
    }
}

2. 一维数组

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];
    }
}