【leetcode】1269. Number of Ways to Stay in the Same Place After Some Steps
2024-09-05 08:58:37
题目如下:
You have a pointer at index
0
in an array of sizearrLen
. At each step, you can move 1 position to the left, 1 position to the right in the array or stay in the same place (The pointer should not be placed outside the array at any time).Given two integers
steps
andarrLen
, return the number of ways such that your pointer still at index0
after exactlysteps
steps.Since the answer may be too large, return it modulo
10^9 + 7
.Example 1:
Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, StayExample 2:
Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, StayExample 3:
Input: steps = 4, arrLen = 2
Output: 8Constraints:
1 <= steps <= 500
1 <= arrLen <= 10^6
解题思路:记dp[i][j]为移动i次后恰好位于下标j的次数,要使得第i步移动到j,那么第i-1步所处的位置就只能是 [j-1,j,j+1],所以有dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] 。
代码如下:
class Solution(object):
def numWays(self, steps, arrLen):
"""
:type steps: int
:type arrLen: int
:rtype: int
"""
arrLen = min(arrLen,steps) dp = [[0] * (arrLen) for _ in range(steps+1)] dp[1][0] = 1
dp[1][1] = 1 for i in range(1,steps+1):
for j in range(len(dp[i])):
dp[i][j] += dp[i-1][j]
if j - 1 >= 0 and j - 1 < len(dp[i]):
dp[i][j] += dp[i-1][j-1]
if j + 1 < len(dp[i]):
dp[i][j] += dp[i-1][j+1] return dp[-1][0] % (10**9 + 7)
最新文章
- Android GPS应用开发
- BZOJ 2006: [NOI2010]超级钢琴
- iOS开发UI中懒加载的使用方法
- Mysql-学习笔记(==》集合函数与分组四)
- 线程入门之优先级priority
- 配置Synergy(Server : XP, client: Win7)
- Git操作指南(2) —— Git Gui for Windows的建库、克隆(clone)、上传(push)、下载(pull)、合并(转)
- linux下拷贝整个目录
- Linux挂载U盘
- JS时间的计算,当前日期加一天或者几天的计算
- vim+ctags+cscope工具
- arrowTip 提示
- Xcode Could not load NIB 的一个问题解决
- Saltstack_使用指南06_远程执行-指定目标
- zabbix异常信息修改已确认,为未确认
- DML_DDL_触发器
- pat 团体赛练习题集 L2-006. 树的遍历
- File操作-将txt里的内容写入到数据库表
- 大数据抓取采集框架(摘抄至http://blog.jobbole.com/46673/)
- android RadioButton文字居中的方法