Posted on 2024-01-26 19:58
Uriel 阅读(5)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
给出二维grid的长度高度m宽度n，和初始球在的位置(startRow, startColumn)，问经过最多maxMove步，每次可以移动球到上下左右七种一格，有几种方式出界，DP
用一个临时变量t保存上一轮dp的状态，可以节省空间
#576
#Runtime: 118 ms (Beats 39.13%)
#Memory: 11.7 MB (Beats 100%)
class Solution(object):
def findPaths(self, m, n, maxMove, startRow, startColumn):
"""
:type m: int
:type n: int
:type maxMove: int
:type startRow: int
:type startColumn: int
:rtype: int
"""
MOD = 10**9+7
dp = [[0] * n for _ in xrange(m)]
dp[startRow][startColumn] = 1
cnt = 0
for _ in xrange(1, maxMove + 1):
t = [[0] * n for _ in xrange(m)]
for i in xrange(m):
for j in xrange(n):
if i == m - 1:
cnt = (cnt + dp[i][j]) % MOD
if j == n - 1:
cnt = (cnt + dp[i][j]) % MOD
if i == 0:
cnt = (cnt + dp[i][j]) % MOD
if j == 0:
cnt = (cnt + dp[i][j]) % MOD
t[i][j] = ((dp[i - 1][j] if i > 0 else 0) % MOD + (dp[i + 1][j] if i < m - 1 else 0) % MOD + (dp[i][j - 1] if j > 0 else 0) % MOD + (dp[i][j + 1] if j < n - 1 else 0) % MOD) % MOD
dp = t
return cnt