# Maximum trailing zeros of the path

Problems:

A table with $$n$$ rows and $$m$$ columns is filled with number from $$1$$ to $$100$$ (duplication allowed). The player starts at $$(1, 1)$$. He can only move right or down. The goal is to reach $$(n, m)$$. Let $$S$$ be the product of numbers the player has met along the way to $$(n, m)$$. Find maximum number of trailing zeros of $$S$$ if the player moves optimally.

What I think about this problem is to use Dynamic Programming. $$S$$ is equal to $$2^x\times5^y\times other\ primes$$ so the answer should be $$min(x, y)$$ but finding maximum $$x$$ or $$y$$ is not optimal. $$min(x, y)$$ instead should be maximized. Please help with this problem.

For each cell $$(i,j)$$, store the set of possible pairs $$(x,y)$$'s.
Now, DP by scanning row-major from top row to bottom row, for each cell $$(i,j)$$, only needs to consider $$(i,j-1)$$ and $$(i-1,j)$$ (if any), either choose or not to choose $$(i,j)$$. So from the stored set in $$(i,j-1)$$ and $$(i-1,j)$$, compute $$(i,j)$$'s set easily.
• My idea is to let $DP(i, j ,k)$ equals to the maximum 2s at $(i, j)$ with $k$ 5s. The transition would be $DP(i, j, k) = max(DP(i-1, j, k-P_5), DP(i, j-1, k-P_5)) + P_2$ for arbitrary $k$ where $P_2$ and $P_5$ are number of 2s and 5s in cell $(i, j)$ respectively. Thanks for your help. It really help me solve this problem. – PeppaPig Sep 30 '18 at 4:57