leetcode1269. 停在原地的方案数【简单DP】

淡淡的烟草味﹌ 2023-01-20 15:59 13阅读 0赞

有一个长度为 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 <= 500  
1 <= arrLen <= 10^6

class Solution {
    public:
        int numWays(int steps, int arrLen) {
            int n = min(steps, arrLen-1);
            int* d = new int[n+1];
            const int mod = 1e9+7;
            d[0] = 1;
            for(int i = 1;i<=n;i++)
                d[i]=0;
            while(steps--)
            {
                int pre,p;
                for(int i = 0;i<=n;i++)
                {
                    pre = d[i];
                    d[i]=((d[i]+(i-1>=0?p:0))%mod+(i+1<=n?d[i+1]:0))%mod;
                    p = pre;
                }
            }
            return d[0];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode_因式分解_简单_263.丑数

目录 1.题目 2.思路 3.代码实现（Java） 1.题目丑数就是只包含质因数 2、3 和 5 的正整数。给你一个整数 n ，请你判断

悠悠/ 2023年10月06日 23:25/ 0 赞/ 40 阅读

相关 LeetCode_原地修改_简单_448.找到所有数组中消失的数字

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给你一个含 n 个整数的数组 nums ，其中 nums\[i\] 在区间 \[1

旧城等待，/ 2023年10月06日 22:42/ 0 赞/ 27 阅读

相关多重集组合数简单dp

1 include <cstdio> 2 include <iostream> 3 4 using namespace std;

我就是我/ 2023年07月12日 05:05/ 0 赞/ 15 阅读

相关 leetcode1269. 停在原地的方案数【简单DP】

有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。给你两个

淡淡的烟草味﹌/ 2023年01月20日 15:59/ 0 赞/ 14 阅读

相关 2020-12-11-天池-汇丰专场-个人赛-04-停在原地的方案数

[ link ][link] 停在原地的方案数难度难度: ★☆☆☆ 题目描述 -------------------- 有一个长度为 arrLe

待我称王封你为后i/ 2022年12月28日 01:50/ 0 赞/ 13 阅读

相关 [leetcode] 279. Perfect Squares（DP）（平方数）

Given a positive integer n, find the least number of perfect square numbers (for example

青旅半醒/ 2022年10月02日 11:59/ 0 赞/ 162 阅读

相关 Leetcode 62. 不同路径（简单DP）

题目重述一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在

柔情只为你懂/ 2022年09月03日 13:14/ 0 赞/ 197 阅读

相关 leetcode 115. Distinct Subsequences 简单DP变形+一个必须要学会的DP问题

Given a string S and a string T, count the number of distinct subsequences of S which eq

小咪咪/ 2022年06月08日 04:16/ 0 赞/ 152 阅读

相关停正在运行的job

1.找出正在执行的JOB编号及其会话编号 SELECT SID,JOB FROM DBA\_JOBS\_RUNNING; 停止该JOB的执行 EXEC

向右看齐/ 2022年04月01日 14:40/ 0 赞/ 240 阅读

相关 POJ-1269—Intersecting Lines（简单计算几何）

Intersecting Lines <table> <tbody> <tr>

青旅半醒/ 2022年03月29日 09:30/ 0 赞/ 219 阅读