1444. Number of Ways of Cutting a Pizza
Brute force
time complexity C((m + n) k mn)
class Solution:
def ways(self, pizza: List[str], k: int) -> int:
m = len(pizza)
n = len(pizza[0])
MOD = 10 ** 9 + 7
@cache
def backtrack(t, l , c):
if c == 0:
for i in range(t, m):
for j in range(l, n):
if pizza[i][j] == 'A':
return 1
return 0
tt, ll = None, None
for i in range(t, m - 1):
for j in range(l, n):
if pizza[i][j] == 'A':
tt = i
break
if tt != None:
break
for i in range(l, n - 1):
for j in range(t, m):
if pizza[j][i] == 'A':
ll = i
break
if ll != None:
break
if tt == None and ll == None:
return 0
res = 0
if tt != None:
for i in range(tt+1, m):
res += backtrack(i, l, c-1)
res %= MOD
if ll != None:
for i in range(ll+1, n):
res += backtrack(t, i, c-1)
res %= MOD
return res % MOD
return backtrack(0, 0, k - 1)
Optimize the repetitive calculation by preSum
class Solution:
def ways(self, pizza: List[str], k: int) -> int:
m = len(pizza)
n = len(pizza[0])
MOD = 10 ** 9 + 7
preSum = [[0] * (n + 1) for i in range(m + 1)]
# for i in range(1, m + 1):
# for j in range(1, n + 1):
# presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1]
# if pizza[i-1][j-1] == 'A':
# presum[i][j] += 1
for i in range(m - 1, -1 , -1):
for j in range(n - 1, -1, -1):
preSum[i][j] = preSum[i+1][j] + preSum[i][j+1] - preSum[i+1][j+1]
if pizza[i][j] == 'A':
preSum[i][j] += 1
@cache
def backtrack(t, l , c):
if preSum[t][l] == 0:
return 0
if c == 0:
return 1
res = 0
for i in range(t+1, m):
# diff = apple counts for pizza t... i row(not include i)
if preSum[t][l] - preSum[i][l] > 0:
res += backtrack(i, l, c-1)
res %= MOD
for i in range(l+1, n):
# diff = apple counts for pizza l... i col(not include i)
if preSum[t][l] - preSum[t][i] > 0:
res += backtrack(t, i, c-1)
res %= MOD
return res % MOD
return backtrack(0, 0, k - 1)