Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出二维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






















只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理