multiply numbers on all paths and get a number with minimum number of zeros

Question

I have m*n table which each entry have a value .

start position is at top left corner and I can go right or down until I reach lower right corner.

I want a path that if I multiply numbers on that path I get a number that have minimum number of zeros in it's right side .

example:

   1 2 100
   5 5 4

possible paths :

1*2*100*4=800
1*2*5*4= 40
1*5*5*4= 100

Solution : 1*2*5*4= 40 because 40 have 1 zero but other paths have 2 zero.

easiest way is using dfs and calculate all paths. but it's not efficient.

I'm looking for an optimal substructure for solving it using dynammic programming.

After thinking for a while I came up to this equation :

T(i,j) = CountZeros(T(i-1,j)*table[i,j]) < CountZeros(T(i,j-1)*table[i,j]) ?
                 T(i-1,j)*table[i,j] : T(i,j-1)*table[i,j]

Code :

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
using Table = vector<vector<int>>;
const int rows = 2;
const int cols = 3;
Table memo(rows, vector<int>(cols, -1));

int CountZeros(int number)
{
    if (number < 0)
        return numeric_limits<int>::max();
    int res = 0;
    while (number != 0)
    {
        if (number % 10 == 0)
            res++;
        else break;
        number /= 10;
    }
    return res;
}


int solve(int i, int j, const Table& table)
{
    if (i < 0 || j < 0)
        return -1;

    if (memo[i][j] != -1)
        return memo[i][j];

    int up = solve(i - 1, j, table)*table[i][j];
    int left = solve(i, j - 1, table)*table[i][j];

    memo[i][j] = CountZeros(up) < CountZeros(left) ? up : left;

    return memo[i][j];
}
int main()
{
    Table table =
    {
        { 1, 2, 100 },
        { 5, 5, 4 }
    };

    memo[0][0] = table[0][0];
    cout << solve(1, 2, table);

}

(Run )

But it is not optimal (for example in above example it give 100 )

Any idea for better optimal sub-structure ? can I solve it with dynammic programming ?!

Answer 1

Let's reconsider the Bellman optimality equation for your task. I consider this as a systematic approach to such problems (whereas I often don't understand DP one-liners). My reference is the book of Sutton and Barto.

The state in which your system is can be described by a triple of integer numbers (i,j,r) (which is modeled as a std::array<int,3>). Here, i and j denote column and row in your rectangle M = m_{i,j}, whereas r denotes the multiplication result.

Your actions in state (i,j,r) are given by going right, with which you end in state (i, j+1, r*m_{i,j+1}) or by going down which leads to the state (i+1, j, r*m_{i+1,j}).

Then, the Bellman equation is given by

v(i,j,r) = min{ NullsIn(r*m_{i+1,j}) - NullsIn(r) + v_(i+1,j, r*m_{i+1,j})
                NullsIn(r*m_{i,j+1}) - NullsIn(r) + v_(i,j+1, r*m_{i,j+1}) }

The rationale behind this equation is the following: NullsIn(r*m_{i+1,j}) - NullsIn(r) denotes the zeros you have to add when you take one of the two actions, i.e. the instant penalty. v_(i+1,j, r*m_{i+1,j}) denotes the zeros in the state you get to when you take this action. Now one wants to take the action which minimizes both contributions.

What you need further is only a function int NullsIn(int) which returns the nulls in a given integer. Here is my attempt:

int NullsIn(int r)
{
    int ret=0;
    for(int j=10; j<=r; j*=10)
    {
        if((r/j) * j == r)
            ++ret;
    }
    return ret;
}

For convenience I further defined a NullsDifference function:

int NullsDifference(int r, int m)
{
    return NullsIn(r*m) - NullsIn(r);
}

Now, one has to do a backwards iteration starting from the initial state in the right bottom element of the matrix.

int backwardIteration(std::array<int,3> state, std::vector<std::vector<int> > const& m)
{
    static std::map<std::array<int,3>, int> memoization;
    auto it=memoization.find(state);
    if(it!=memoization.end())
        return it->second;

    int i=state[0];
    int j=state[1];
    int r=state[2];

    int ret=0;
    if(i>0 && j>0)
    {
        int inew=i-1;
        int jnew=j-1;

        ret=std::min(NullsDifference(r, m[inew][j]) + backwardIteration({inew,j,r*m[inew][j]}, m),
                     NullsDifference(r, m[i][jnew]) + backwardIteration({i,jnew,r*m[i][jnew]}, m));
    }
    else if(i>0)
    {
        int inew=i-1;
        ret= NullsDifference(r, m[inew][j]) + backwardIteration({inew,j,r*m[inew][j]}, m);
    }
    else if(j>0)
    {
        int jnew=j-1;
        ret= NullsDifference(r, m[i][jnew]) + backwardIteration({i,jnew,r*m[i][jnew]}, m);
    }

    memoization[state]=ret;
    return ret;
}

This routine is called via

int main()
{
    int ncols=2;
    int nrows=3;
    std::vector<std::vector<int> > m={{1,2,100}, {5,5,4}};    
    std::array<int,3> initialState = {ncols-1, nrows -1, m[ncols-1][nrows - 1]};

    std::cout<<"Minimum number of zeros: "backwardIteration(initialState, m)<<"\n"<<std::endl;
}

For your array, it prints out the desired 1 for the number of zeros.

Here is a live demo on Coliru.

---

EDIT

Here is an important thing: in production, you usually don't call backwardIteration as I did because it takes an exponentially increasing number of recursive calls. Rather, you start in the top left and call it, then store the result. Next you go left and down and each time call backwardIteration where you now use the previously stored result. And so on.

In order to do this, one needs a memoization concept within the function backwardIteration, which returns the already stored result instead of invoking another recursive call.

I've added memoization in the function call above. Now you can loop through the array from left top to right bottom in any way you like -- but prefereably take small steps, such as row-by-row, column-by-column, or rectangle-for-rectangle.

In fact, this and only this is the spirit of Dynamic Programming.