我该如何使用DP来解决这个问题？

Question

我该如何使用DP来解决这个问题？

algorithmrecursionmatrixdynamic-programming

7

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

有一个由非负整数构成的 n × n 方阵。你需要在其中找到这样一条路径：

从方阵的左上角出发；
每次只能向右或向下移动一个方格；
最终到达方阵右下角。

此外，如果将路径上经过的所有数字相乘，结果应该是“尽量少”的，也就是说，它应该以可能最小的末尾零数结束。

输入
第一行为一个整数 n（2 ≤ n ≤ 1000），表示矩阵的大小。接下来的 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示例：

输入：

输出：

0
DDRR

- rohansingh

你需要比几行 C 代码更多的工作来解决这个问题。我建议使用递归方法。 - Tim Biegeleisen

@vish4071，那我该如何改进它呢？ - rohansingh

谁说这个产品只能是2和5的倍数？例如：1 * 2 * 3 * 6 * 9 = 324 - Tim Biegeleisen

Сйат»╣2тњї5уџёУ«Ау«ЌТў»ТГБуА«уџёсђѓСйєтѕХСйю2СИфуЪЕжўхт╣ХСИЇтЈ»тЈќсђѓСйаСй┐ућеcppтљЌ№╝Ъ - vish4071

@vish4071，好的，是的，我使用C++。非常感谢你的帮助。 :) - rohansingh

显示剩余5条评论

4个回答

0

这里是代码。我使用了pair<int,int>来存储矩阵中2和5的因子。

#include<vector>
#include<iostream>
using namespace std;

#define pii pair<int,int> 
#define F first 
#define S second
#define MP make_pair

int calc2(int a){
    int c=0;
    while(a%2==0){
        c++;
        a/=2;
    }
    return c;
}

int calc5(int a){
    int c=0;
    while(a%5==0){
        c++;
        a/=5;
    }
    return c;
}

int mini(int a,int b){
    return a<b?a:b;
}

pii min(pii a, pii b){
    if(mini(a.F,a.S) < mini(b.F,b.S))
        return a;
    return b;
}

int main(){
    int n;
    cin>>n;
    vector<vector<pii > > v;
    vector<vector<int> > path;

    int i,j;
    for(i=0;i<n;i++){
        vector<pii > x;
        vector<int> q(n,0);
        for(j=0;j<n;j++){
            int y;cin>>y;
            x.push_back(MP(calc2(y),calc5(y)));   //I store factors of 2,5 in the vector to calculate
        }
        x.push_back(MP(100000,100000));     //padding each row to n+1 elements (to handle overflow in code)
        v.push_back(x);
        path.push_back(q);     //initialize path matrix to 0
    }

    vector<pii > x(n+1,MP(100000,100000));
    v.push_back(x);               //pad 1 more row to handle index overflow

    for(i=n-1;i>=0;i--){
        for(j=n-1;j>=0;j--){          //move from destination to source grid
            if(i==n-1 && j==n-1)
                continue;

            //here, the LHS of condition in if block is the condition which determines minimum number of trailing 0's. This is the same condition that is used to manipulate "v" for getting the same result. 
            if(min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)) == MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S))
                path[i][j] = 1;         //go down
            else
                path[i][j] = 2;         //go right
            v[i][j] = min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S));
        }
    }

    cout<<mini(v[0][0].F, v[0][0].S)<<endl;   //print result
    for(i=0,j=0;i<=n-1 && j<=n-1;){           //print path (I don't know o/p format)
        cout<<"("<<i<<","<<j<<") -> ";
        if(path[i][j]==1)
            i++;
        else
            j++;
    }

    return 0;
}

这段代码在我检查的测试用例中表现良好。如果您对此代码有任何疑问，请在评论中询问。

编辑：基本思路。
到达目的地只有两个选择。我从目的地开始，避免了前面路径计算的问题，因为如果两者具有相同的最小值，那么我们选择其中任意一个。如果已经计算出了到目的地的路径，则无论我们选择哪一个都没有关系。

而“最小值”是为了检查哪一对更合适。如果一对比另一对少2个或5个，它将产生较少的0。

- vish4071

@NicoSchertler，这两种情况都会输出0。 - vish4071

@vish4071，你能解释一下条件，也就是“min”条件，以及为什么要从结尾开始吗？还有，解决这个问题的逻辑是什么？ - rohansingh

@NicoSchertler，我认为这没有问题。所以我从目标移动到源头。因此，“前方路径”已经被计算为最小值。你提供的测试案例的每个排列都会产生“0”作为输出。 - vish4071

@NicoSchertler，感谢您提供的测试用例。在检查了您之前提供的用例后，我尝试在链接上提交代码。显然它给出了WA。:( - vish4071

是的，那就是它。但我从目的地开始的原因已经不再有效了。所以答案并不完全正确。我会加以改进。 - vish4071

显示剩余2条评论

0

这里提供了一个使用Javascript和函数式编程的解决方案建议。它依赖于几个函数：

核心函数是smallest_trailer，它通过网格进行递归。我选择了4个可能的方向，左“L”，右“R”，下“D”和“U”。不可能在同一单元格上通过两次。选择的方向是具有最小尾随零数的方向。尾随零的计数专门用于另一个函数。
函数zero_trailer(p,n,nbz)假设您到达一个值为p的单元格，同时已经有一个累加器n并且在路上遇到了nbz个零。该函数返回一个带有两个元素的数组，即新的零数和新的累加器。累加器将是2或5的幂。该函数使用辅助函数pow_2_5(n)，该函数返回n中的2和5的幂。
其他函数更多是轶事：deepCopy(arr)对数组arr进行标准深度复制，out_bound(i,j,n)如果单元格(i,j)超出大小为n的网格，则返回true，myMinIndex(arr)返回二维数组的最小索引（每个子数组包含尾随零的数量和路径作为字符串）。仅在子数组的第一个元素上取最小值。
MAX_SAFE_INTEGER是一个（大）常量，用于当路径错误时（例如超出边界）的最大尾随零数。

这里是代码，它适用于上面评论和原始链接中给出的示例。

var MAX_SAFE_INTEGER = 9007199254740991;

function pow_2_5(n) {
  // returns the power of 2 and 5 inside n
  function pow_not_2_5(k) {
    if (k%2===0) {
      return pow_not_2_5(k/2);
    }
    else if (k%5===0) {
      return pow_not_2_5(k/5);
    }
    else {
      return k;
    }
  }
  return n/pow_not_2_5(n);
}

function zero_trailer(p,n,nbz) {
  // takes an input two numbers p and n that should be multiplied and a given initial number of zeros (nbz = nb of zeros)
  // n is the accumulator of previous multiplications (a power of 5 or 2)
  // returns an array [kbz, k] where kbz is the total new number of zeros (nbz + the trailing zeros from the multiplication of p and n)
  // and k is the new accumulator (typically a power of 5 or 2)
  function zero_aux(k,kbz) {
    if (k===0) {
      return [1,0];
    }
    else if (k%10===0) {
      return zero_aux(k/10,kbz+1);
    }
    else {
      return [kbz,k];
    }
  }
  return zero_aux(pow_2_5(p)*n,nbz);  
}

function out_bound(i,j,n) {
  return !((i>=0)&&(i<n)&&(j>=0)&&(j<n));
}

function deepCopy(arr){
  var toR = new Array(arr.length);
  for(var i=0;i<arr.length;i++){
    var toRi = new Array(arr[i].length);
    for(var j=0;j<arr[i].length;j++){
      toRi[j] = arr[i][j];
    }
    toR[i] = toRi;
  }
  return toR;
}

function myMinIndex(arr) {
  var min = arr[0][0];
  var minIndex = 0;
  for (var i = 1; i < arr.length; i++) {
      if (arr[i][0] < min) {
          minIndex = i;
          min = arr[i][0];
      }
  }
  return minIndex;
}

function smallest_trailer(grid) {
  var n = grid.length;
  function st_aux(i,j,grid_aux, acc_mult, nb_z, path) {

    if ((i===n-1)&&(j===n-1)) {          
      var tmp_acc_nbz_f = zero_trailer(grid_aux[i][j],acc_mult,nb_z);
      return [tmp_acc_nbz_f[0], path];
    }
    else if (out_bound(i,j,n)) {
      return [MAX_SAFE_INTEGER,[]];
    }
    else if (grid_aux[i][j]<0) {
      return [MAX_SAFE_INTEGER,[]];
    }
    else {
      var tmp_acc_nbz = zero_trailer(grid_aux[i][j],acc_mult,nb_z) ;
      grid_aux[i][j]=-1;
      var res = [st_aux(i+1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"D"), 
                 st_aux(i-1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"U"),
                 st_aux(i,j+1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"R"),
                 st_aux(i,j-1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"L")];
      return res[myMinIndex(res)];      
    }
  }
  return st_aux(0,0,grid, 1, 0, "");
}

myGrid = [[1, 25, 100],[2, 1, 25],[100, 5, 1]];
console.log(smallest_trailer(myGrid)); //[0,"RDDR"]
myGrid = [[1, 2, 100],[25, 1, 5],[100, 25, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRDR"]
myGrid = [[1, 10, 1, 1, 1],[1, 1, 1, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1]];
console.log(smallest_trailer(myGrid)); //[0,"DRRURRDDDD"]

- isanco

0

这是我的动态规划解决方案。

https://app.codility.com/demo/results/trainingAXFQ5B-SZQ/

为了更好地理解，我们可以简化任务并假设矩阵中没有零（即矩阵仅包含正整数），那么Java解决方案将如下：

class Solution {
    public int solution(int[][] a) {
        int minPws[][] = new int[a.length][a[0].length];

        int minPws2 = getMinPws(a, minPws, 2);
        int minPws5 = getMinPws(a, minPws, 5);
        return min(minPws2, minPws5);
    }

    private int getMinPws(int[][] a, int[][] minPws, int p) {
        minPws[0][0] = pws(a[0][0], p);
        //Fullfill the first row
        for (int j = 1; j < a[0].length; j++) {
            minPws[0][j] = minPws[0][j-1] + pws(a[0][j], p);
        }
        //Fullfill the first column
        for (int i = 1; i < a.length; i++) {
            minPws[i][0] = minPws[i-1][0] + pws(a[i][0], p);
        }
        //Fullfill the rest of matrix
        for (int i = 1; i < a.length; i++) {
            for (int j = 1; j < a[0].length; j++) {
                minPws[i][j] = min(minPws[i-1][j], minPws[i][j-1]) + pws(a[i][j], p);
            }
        }

        return minPws[a.length-1][a[0].length-1];
    }

    private int pws(int n, int p) {
        //Only when n > 0
        int pws = 0;
        while (n % p == 0) {
            pws++;
            n /= p;
        }
        return pws;
    }

    private int min(int a, int b) {
        return (a < b) ? a : b;
    }
}

- Anton Fil

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- sve · Accepted Answer

如果您只关心末尾的零的数量，那么您只需要考虑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的最优路径上的2的数量为a，5的最优路径上的5的数量为b。不失一般性地假设两条最优路径中的最小值是2的幂（即a < b）。让最小路径上的5的数量为c。现在的问题是：这条路径上是否有与2的数量相同的5（即c >= a）？假设答案是否定的。这意味着最小路径上的5比2少（即c < a）。由于5的最优路径的最优值为b，因此我们得到每个5的路径中至少有b个5。这也应该对最小路径成立。这意味着c > b。我们有c < a，所以a > b，但最初的假设是a < b。矛盾。

注2

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