Maximum trailing zeros of the path

Question

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.

Answer 1

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.

Try to finish the above idea in details. And then code it in your favorite programming language will quickly improve your DPing skill.