Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个由.和A组成的二维矩阵,A表示该个点有apple。每次可以横切或竖切,问切k-1刀将矩阵分为k块有多少种方式(每块至少包含一个A)
完全没想出如何记录状态,参考了Discussion:https://leetcode.com/problems/number-of-ways-of-cutting-a-pizza/solutions/3360818/easy-solutions-in-java-python-and-c-look-at-once-with-exaplanation


 1 #1444
 2 #Runtime: 203 ms (Beats 68%)
 3 #Memory: 14.1 MB (Beats 74%)
 4 
 5 class Solution(object):
 6     def ways(self, pizza, k):
 7         """
 8         :type pizza: List[str]
 9         :type k: int
10         :rtype: int
11         """
12         m = len(pizza)
13         n = len(pizza[0])
14         dp = [[[None] * n for _ in range(m)] for _ in range(k)]
15         preSum = [[0] * (n+1) for _ in range(m + 1)]
16         for r in range(m - 1, -1, -1):
17             for c in range(n - 1, -1, -1):
18                 preSum[r][c] = preSum[r+1][c] + preSum[r][c+1] - preSum[r+1][c+1] + (pizza[r][c] == 'A')
19 
20         def DFS(m, n, k, r, c, dp):
21             if preSum[r][c] == 0:
22                 return 0
23             if k == 0:
24                 return 1
25             if dp[k][r][c] is not None:
26                 return dp[k][r][c]
27             ans = 0
28             for nr in range(r + 1, m):
29                 if preSum[r][c] - preSum[nr][c] > 0:
30                     ans = (ans + DFS(m, n, k - 1, nr, c, dp)) % 1000000007
31             for nc in range(c+1, n):
32                 if preSum[r][c] - preSum[r][nc] > 0:
33                     ans = (ans + DFS(m, n, k - 1, r, nc, dp)) % 1000000007
34             dp[k][r][c] = ans
35             return ans
36 
37         return DFS(m, n, k - 1, 0, 0, dp)

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