Where was I wrong in this recursive solution? There is an iterative dp solution for this but I want to know my mistake here. Anybody please let me know!

Question

0.00/5 (No votes)

See more:

Given a gold mine (M) of n*m dimensions. Each field in this mine contains a positive integer which is the amount of gold in tons. Initially the miner is at first column but can be at any row. He can move only (right->,right up /,right down\) that is from a given cell, the miner can move to the cell diagonally up towards the right or right or diagonally down towards the right. Your task is to find out maximum amount of gold which he can collect.

Input : M[][] = {{1, 3, 3},
{2, 1, 4},
{0, 6, 4}};
Output : 12
{(1,0)->(2,1)->(2,2)}

Input: M[][] = {{1, 3, 1, 5},
{2, 2, 4, 1},
{5, 0, 2, 3},
{0, 6, 1, 2}};
Output : 16
(2,0) -> (1,1) -> (1,2) -> (0,3) OR
(2,0) -> (3,1) -> (2,2) -> (2,3)

What I have tried:

C++

#include<iostream>
#include<vector>
using namespace std;
int func(vector<vector<int>>a,int p,int q,int n,int m,int ans)
{
    if(q==m-1)
    {
     return ans;
    }
    if(p==0)
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),func(a,p+1,q+1,n,m,ans+a[p+1][q+1]));
    }
    else if(p==n-1)
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),func(a,p-1,q+1,n,m,ans+a[p-1][q+1]));
    }
    else
    {
     return max(func(a,p,q+1,n,m,ans+a[p][q+1]),
       max(func(a,p-1,q+1,n,m,ans+a[p-1][q+1]),func(a,p+1,q+1,n,m,ans+a[p+1][q+1])));
    }
}
int main()
 {
	//code
	int t;
	cin>>t;
	while(t--)
	{
	    int n,m;
	    cin>>n>>m;
	    vector<vector<int>>a;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            int temp;
	            cin>>temp;
	            a[i].push_back(temp);
	        }
	    }
	    int p=0;
	    int q=0;
	    int ans=0;
	    cout<<func(a,p,q,n,m,ans+a[0][0])<<endl;
	}
	return 0;
}

Posted 30-Jun-19 8:07am

Raghurss

Updated 1-Jul-19 0:21am

KarstenK

v2

Add a Solution

Comments

[no name] 30-Jun-19 14:52pm

Nobody's going to be able to decipher your meaningless variable names ... including yourself.

Raghurss 1-Jul-19 9:32am

🤐😅

4 solutions

Solution 1

I'm not wading through that mess of code to try and work out what the heck it's supposed to do, such less how it is doing - and the lack of documentation and use of meaningless single character variables is a big factor in that.

So, it's going to be up to you. Run it in the debugger (google will tell you how to use it) and watch carefully to find out exactly what is happening.

But ... if q starts out equal to m, and p is equal to zero, it will always blow the stack ...

Posted 30-Jun-19 9:09am

OriginalGriff

Comments

Raghurss 1-Jul-19 9:21am

Apologies for that meaningless stuff. I was in a hurry to get my mistake! Yeah I'll do that. Thanks!

Solution 2

Quote:

C++

a[i].push_back(temp);

Not sure how the compiler will handle this, but std::vector is always initialized to be empty unless specified otherwise. Therefore a[i] is not defined for any value of i. You need to resize a before accessing it.

Posted 30-Jun-19 21:42pm

Stefan_Lang

Comments

Raghurss 1-Jul-19 9:22am

Oh! Thank you for the suggestion.

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Accepted Answer · 2019-07-01T00:22:00

As starting point, try

C++

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


using Matrix = vector< vector <int > >;

int maxsum( const Matrix & m, size_t r, size_t c)
{
  if ( c == m[r].size()-1)
    return m[r][c];

  int contrib = maxsum( m,r, c+1); //same row contribution

  if ( r == 0)
    contrib = max( contrib, maxsum( m, r+1, c+1));
  else if ( r == m.size()-1)
    contrib = max( contrib, maxsum(m, r-1, c+1));
  else
    contrib = max( contrib, max( maxsum(m, r+1, c+1), maxsum(m, r-1, c+1)));

  return (m[r][c] + contrib);
}

int main()
{
  size_t R,C; // R rows, C columns
  cin >> R >> C;

  vector < vector <int> > m(R);


  for (auto & v : m)
    for (size_t c = 0; c < C; ++c)
    {
      int i;
      cin >> i;
      v.push_back(i);
    }


  int maxgold = 0;
  for (size_t r = 0; r < R; ++r)
  {
    int gold = maxsum(m, r, 0);
    if  (maxgold < gold)
      maxgold = gold;
  }

  cout << "max gold = " << maxgold << endl;

}

KarstenK · Accepted Answer · 2019-06-30T21:43:00

It is up to you to debug the code, but it will help you when use better names and some structered data like structs for the position. This will also help to clearify the structure of your code. Along with that you should do more output like "found X gold at (x,y)".

bonus tip 1: use some coded mine array for debugging, so you dont need to input it.
bonus tip 2: use temporary values in the "func" code
bonus tip 3: use the const and reference in the call of the subroutine

C++

const vector<vector<int>> &a

to avoid creating copies of the vector in the calls. It will improve speed and make the debugging easier-

Where was I wrong in this recursive solution? There is an iterative dp solution for this but I want to know my mistake here. Anybody please let me know!

4 solutions

Solution 4

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0