我将如何使用DP解决此问题？

Question

问题链接：http : //codeforces.com/contest/2/problem/B

有一个由非负整数组成的方阵n？×？n。您应该在上面找到这样的方法

从矩阵的左上角单元格开始；接下来的每个单元格都位于当前单元格的右侧或下方；方式在右下角的单元格中结束。此外，如果我们将所有数字相乘，结果应该是最小的“舍入”。换句话说，它应以尽可能少的零结尾。

输入第一行包含一个整数n（2 ??? n ??? 1000），n是矩阵的大小。然后跟随n行包含矩阵元素（不超过10 ^ 9的非负整数）。

输出在第一行中，打印最少数量的尾随零。在第二行中打印相应的方式本身。

我想到了以下几点：最后，无论答案是什么，它都应包含2和5的最小幂。因此，我所做的是，对于输入矩阵中的每个条目，我都计算了2和5的幂，并将它们存储在单独的矩阵中。

    for (i = 0; i < n; i++)
    {
        for ( j = 0; j < n; j++)
        {
            cin>>foo;
            matrix[i][j] = foo;
            int n1 = calctwo(foo);   // calculates the number of 2's in factorisation of that number
            int n2 = calcfive(foo); // calculates number of 5's
            two[i][j] = n1;
            five[i][j] = n2;
        }
    }

之后，我这样做了：

for (i = 0; i < n; i++)
{
    for ( j = 0; j < n; j++ )
    {
        dp[i][j] = min(two[i][j],five[i][j]);  // Here, dp[i][j] will store minimum number of 2's and 5's. 
    }
}

但是以上并不是一个有效的答案，我不知道为什么吗？我实施了正确的方法吗？或者，这是解决此问题的正确方法吗？

编辑：这是我计算一个数字的二位数和五位数的功能。

int calctwo (int foo)
{
    int counter = 0;
    while (foo%2 == 0)
    {
        if (foo%2 == 0)
        {
            counter++;
            foo = foo/2;
        }
        else
            break;
    }
    return counter;
}

int calcfive (int foo)
{
    int counter = 0;
    while (foo%5 == 0)
    {
        if (foo%5 == 0)
        {
            counter++;
            foo = foo/5;
        }
        else
            break;
    }
    return counter;
}

编辑2：I / O示例，如链接中所示：

输入：

3
1 2 3
4 5 6
7 8 9

输出：

0
DDRR

Answer 1

由于您只对尾随零的数量感兴趣，因此您只需考虑 的幂2，5您可以将其保存在两个单独的nxn数组中。所以对于数组

1 2 3
4 5 6
7 8 9

你只需要保留数组

the powers of 2    the powers of 5       
0 1 0              0 0 0
2 0 1              0 1 0
0 3 0              0 0 0

问题的见解如下。请注意，如果您找到一条使 2 的幂之和最小的路径和一条使 5 的幂的数和最小的路径，那么答案是这两条路径中具有较低值的路径。因此，您将问题简化为以下经典 dp 问题的两倍应用：找到一条路径，从左上角开始到右下角结束，使其元素的总和最小。同样，按照示例，我们有：

 minimal path for the 
 powers of 2                 value
 * * -                         2
 - * * 
 - - *

 minimal path for the 
 powers of 5                 value
 * - -                         0
 * - - 
 * * *

所以你的答案是

 * - -                      
 * - - 
 * * *

有价值 0

注 1

取两条最优路径中的最小值似乎只给出了一个上限，因此可能会出现一个问题：这个界限是否真的实现了？答案是肯定的。为方便起见，设沿 2 的最优路径的 2a个数为 ，沿 5 的最优路径的 5 个数为b。不失一般性，假设两条最优路径中的最小值是 2 的幂（即a < b）。设沿最小路径的 5 个数为c。现在的问题是：这条路径上是否有 5 个和 2 个一样多（即是c >= a？）。假设答案是否定的。这意味着沿着最小路径（即c < a）的5 少于 2 。由于 5' 的最优值bb里面有5个。对于最小路径，这也应该是正确的。这意味着c > b. 我们有c < a这么a > b但最初的设想是a < b。矛盾。

笔记2

您可能还需要考虑0矩阵中有元素的情况。当乘积为 1 时，我假设尾随零的数量。在这种情况下，如果算法产生的结果值大于 1，您应该输出 1 并打印通过 element 的路径0。