Posted on 2024-01-26 19:58
Uriel 閱讀(48)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
給出二維grid的長度高度m寬度n，和初始球在的位置(startRow, startColumn)，問經(jīng)過最多maxMove步，每次可以移動球到上下左右七種一格，有幾種方式出界，DP
用一個臨時變量t保存上一輪dp的狀態(tài)，可以節(jié)省空間
#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