题目
解法：
Weekly Contest 289的题目，自己感觉有点变态，当时没做出来
这道题需要解决一下几个问题：
- 如何数trailing zero
- 如何枚举这些符合条件形状的所有可能性
第一个问题最优解是，所有的0都只可能是2*5得到，所以可以把每个位置数字分解，记录每个数字以2为因子和以5为因子的个数。可以通过一个形状能组成多少个2，5的pair来得到多少个0。由于要累计这些个数，所以使用prefixsum技巧
枚举这些形状可能性最好操作的方案是把每个位置作为形状的turning point，这样就可以每个位置穷举四种组合即可。可以验证即使当前位置在第一行或者第一列（可能会有方向无法组成有效的形状），最后的答案也不会有问题
class Solution:def maxTrailingZeros(self, grid: List[List[int]]) -> int:# helper function to get the number of factors of 2 and 5 in a numberdef helper(num,f):if num % f != 0:return 0return 1 + helper(num // f,f)m,n = len(grid),len(grid[0])# left represents the rowwise left to right prefix sum of factor of 2 and 5 numbersleft = [[[0,0] for _ in range(n)] for _ in range(m)]# top represents the columnwise top to down prefix sum of factor of 2 and 5 numberstop = [[[0,0] for _ in range(n)] for _ in range(m)]# get the prefix sum matrix for rowwisefor i in range(m):for j in range(n):if j == 0:left[i][j] = [helper(grid[i][j],2),helper(grid[i][j],5)]else:a = helper(grid[i][j],2)b = helper(grid[i][j],5)left[i][j][0] = left[i][j-1][0] + aleft[i][j][1] = left[i][j-1][1] + b# get the prefix sum matrix for columnwisefor j in range(n):for i in range(m):if i == 0:top[i][j] = [helper(grid[i][j],2),helper(grid[i][j],5)]else:a = helper(grid[i][j],2)b = helper(grid[i][j],5)top[i][j][0] = top[i-1][j][0] + atop[i][j][1] = top[i-1][j][1] + b# for every grid position, take it as the elbow/tuning point, and span 4 different posibilitiesans = 0for i in range(m):for j in range(n):# columnwise factor 2/5 prefix sum at last row column j;fac2_last_row,fac5_last_row = top[m-1][j]# rowwise factor 2/5 prefix sum at last column row ifac2_last_col,fac5_last_col = left[i][n-1]# factor 2/5 count for the number in current position; this is needed because this place might be added/subtracted twicefac2_curr,fac5_curr = helper(grid[i][j],2),helper(grid[i][j],5)# columnwise factor 2/5 prefix sum at current positionfac2_curr_row, fac5_curr_row = top[i][j]# rowwise factor 2/5 prefix sum at current positionfac2_curr_col, fac5_curr_col= left[i][j]'''case1:000 0 0 '''case1 = min(fac2_curr_row+fac2_curr_col-fac2_curr,fac5_curr_row+fac5_curr_col-fac5_curr)'''case2:000 0 0'''case2 = min(fac2_curr_row+fac2_last_col-fac2_curr_col,fac5_curr_row+fac5_last_col-fac5_curr_col)'''case3:0 0 0 00'''case3 = min(fac2_curr_col+fac2_last_row-fac2_curr_row,fac5_curr_col+fac5_last_row-fac5_curr_row)'''case4:0 0 0 00'''case4 = min(fac2_last_col-fac2_curr_col+fac2_last_row-fac2_curr_row+fac2_curr,fac5_last_col-fac5_curr_col+fac5_last_row-fac5_curr_row+fac5_curr)ans = max(ans,case1,case2,case3,case4)return ans
时间复杂度：O(mnk)，m为函数，n为列数，k可能不是一个常数，代表某个数字做2和5的因子分解的复杂度
空间复杂度：O(m*n)
参考答案链接：
https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/discuss/1955607/Python3-Explanation-with-pictures-prefix-sum.
todo：
实现c++版本，可参考这里：https://leetcode.com/problems/maximum-trailing-zeros-in-a-cornered-path/discuss/1955515/Prefix-Sum-of-Factors-2-and-5