F_JustWei's Studio.

1269. 停在原地的方案数

leetcode 动态规划
字数统计: 358阅读时长: 1 min
2021/05/13 Share

1269. 停在原地的方案数

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

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

给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 steps 次操作以后，指针仍然指向索引 0 处的方案数。

由于答案可能会很大，请返回方案数 模 10^9 + 7 后的结果。

示例 1：

1
2
3
4
5
6
7
输入：steps = 3, arrLen = 2
输出：4
解释：3 步后，总共有 4 种不同的方法可以停在索引 0 处。
向右，向左，不动
不动，向右，向左
向右，不动，向左
不动，不动，不动

示例 2：

1
2
3
4
5
6
7
8
9
输入：steps = 2, arrLen = 4
输出：2
解释：2 步后，总共有 2 种不同的方法可以停在索引 0 处。
向右，向左
不动，不动
示例 3：

输入：steps = 4, arrLen = 2
输出：8

提示：

1
2
1 <= steps <= 500
1 <= arrLen <= 10^6

C++代码：

一维dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
    const int mod = 1e9 + 7;
public:
    int numWays(int steps, int arrLen) {
        long dp[505] = { 1 };
        for (int step = 1; step <= steps; step++) {
            long t = 0;
            for (int i = 0; i < min(min(step + 1, arrLen), steps - step + 1); i++) {
                swap(t, dp[i]);//记录前一个的数据
                dp[i] = (t + dp[i] + dp[i + 1]) % mod;
            }
        }

        return dp[0];
    }
};

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/05/13/1269-%E5%81%9C%E5%9C%A8%E5%8E%9F%E5%9C%B0%E7%9A%84%E6%96%B9%E6%A1%88%E6%95%B0/

发表日期：May 13th 2021, 1:04:27 pm

更新日期：May 13th 2021, 1:14:14 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 1269. 停在原地的方案数
    1. 1.0.1. 示例 1：
    2. 1.0.2. 示例 2：
    3. 1.0.3. 提示：
    4. 1.0.4. C++代码：
Total : 130
2021
2019
leetcode 动态规划 字符串 树 数据结构 C++ STL algorithm 容器 操作系统 软考 Java PTA 计算机网络 UML 迭代器 C JSON 信息安全 模板 多媒体， 软考 数据库 软件工程 排序 Spring 人机交互