Getting from top left to bottom right element of array using dynamic programming

Question

I'm having a hard time thinking of a way to make a solution for a dynamic programming problem. Basically, I have to get from the top left to bottom right element in a NxN array, being able to move only down or right, but I should move to the bigger element and sum it in a variable (get highest score by moving only right and down). F.e., if I have this matrix:

0 1 1

0 4 2

1 1 1

It should move 0-> 1 -> 4 -> 2 -> 1 and print out 8. I've read about dynamic optimizing for a long time now and still can't get to solve this. Would appreciate if anybody could help me. Thanks in advance!

Edit: Thanks @sestus ! I've managed to solve the problem, however the solution is slow and I have to optimize it to perform faster. Here's my solution:

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100;
int arr[MAX][MAX];

int move(int row,int col, int n)
{
if(row >= n || col >= n)
{
    return 0;
}
return max(arr[row][col] + move(row + 1, col, n),
           arr[row][col] + move(row, col + 1, n));
}

int main()
{
int examples, result;
cin>>examples;
int n;
int results[examples];
for(int k =1; k <= examples; k++)
{
    cin >> n;
    int s = 0;
    int i = 0, j = 0;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            cin>> arr[i][j];
        }
    }
    i = 0, j = 0;
    s+=move(i,j, n);
    results[k] = s;
}
for(int k = 1; k <= examples; k++)
{
    cout<<results[k]<<endl;
}
return 0;
}

(The programs actually has to take all the examples and output the answers for all of them at the end). Mind helping me with the optimizing?

Answer 1

I m not going to paste ready-to-go code here, I ll just give you a high level description of the solution.

So what are your possible choices when deciding where to move? You can move either down or right, adding the value of your current block. Your aim is to maximize the sum of the blocks that you have visited till you make it to the bottom-right block. That gives us:

move(row, column):
   //handle the cases when you move out of bounds of the array here
   return(max{array[row,column] + move(row + 1, column),
              array[row,column] + move(row, column + 1)})

For the above to be a complete dynamic programming solution, you ll need to add some memoization e.g get the values of the problems that you 've already solved without having to compute them again. Check this on stackoverflow for more details : Dynamic programming and memoization: bottom-up vs top-down approaches

So for example, take this board:

Notice the two different routes. We 've arrived to the block[1][2] (the one with value 3 that the red and blue lines end) via two different routes. According to the blue route, we moved down-right-right, while we moved right-right-down via the read. The pseudocode I pasted dictates that we are going to take the blue route first, cause we encounter the recursive call move(row + 1, column) prior to the recursive call move(row, column + 1).

So, when we reach the block[1][2] from the red route, we don't actually need to compute this solution again. We 've already done this, back when we were there via the read route! If we kept this solution in an array (or a map / hash table), we 'd be able to just pick the solution without having to compute it again. That's memoization!

Based on the above, you can utilize a map since you 're using c++:

std::map<std::pair<int, int>, int> cache;

And before doing the recursive call, you ll want to check if the pair exist in the map. If it doesn't you add it in the map. So move becomes:

int move(int row,int col, int n)
{
    if(row >= n || col >= n)
    {
        return 0;
    }
    pair<int, int> rowplus_column = make_pair(row + 1,col);
    pair<int, int> row_columnplus = make_pair(row, col + 1);
    int solution_right = 0;
    int solution_down = 0;
    map<char, int>::iterator it;

    it = cache.find(rowplus_column);
    if (it == cache.end())  {
       solution_down = move(row + 1, col);
       cache.insert(rowplus_column, solution_down);
    }
    else {
        solution_down = it->second;
    }
    it = cache.find(row_columnplus);
    if (it == cache.end())  {
       solution_right = move(row, col + 1);
       cache.insert(row_columnplus, solution_right);
    }
    else {
       solution_right = it->second;
    }
    return max(arr[row][col] + solution_down,
           arr[row][col] + solution_right);
}

I am a little rusty in C++, but hopefully you got the idea: Before actually computing the solution, check the map for the pair. If that pair exists, you 've already solved that part of the problem, so get your solution from the map and avoid the recursive call.