CareerCup

dynamic programming...

This comment has been deleted.

Can anyone write the complete code ?

My apologies to not write this before but it was also asked to find the maximum amount of grass eaten by the goat .

<pre lang="c++" line="1" title="CodeMonkey5181" class="run-this">Can anyone check this code although I have tested it twice it runs fine according to me . Also comment on complexity .

#include<iostream>
#include<conio.h>
using namespace std;
int a[4][4] =
{
{ 1,7,5,2 },
{ 5,12,3,6 },
{ 100,9,23,16 },
{ 16,4,5,9 },
};
int m=4,n=4;
int path(int sum , int i , int j)
{
if(j==(n-1)&&i==(m-1))
return sum;
if(i==(m-1))
return path(sum+a[i][j+1],i,j+1);
if(j==(n-1))
return path(sum+a[i+1][j],i+1,j);
else
{
int sum1 = path(sum+a[i+1][j],i+1,j);
int sum2 = path(sum+a[i][j+1],i,j+1);
int sum3 = (sum1>sum2)?sum1:sum2;
return sum3;
}
}
int main()
{
cout<<path(a[0][0],0,0);
getch();
}
</pre>

I wish I had the time. But, here is the approach http :// en.wikipedia.org/ wiki/ Viterbi_algorithm/

DP is the correct one, I think.
dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j];
sub optimal problems and then keep on until the final goal.

The code of the solution in c using Dynamic Programming:

#include<stdio.h>

int main()
{
	// a holds the grass values
	int a[4][4]={
                 { 1,7,5,2 },
                 { 5,12,3,6 },
                 { 100,9,23,16 },
                 { 16,4,5,9 },
               };
	int m=4,n=4;
	
	// sum[i][j] holds the maximum grass that can be eaten if the goat goes from a[i][j] point to a[m-1][n-1]
	// sum[0][0] == the maximum amount of grass the goat eats
	// we build the matrix sum using dynamic programming paradigm
	
	int sum[m][n];
	
	// move[i][j] stores the next best move from a[i][j], that will allow the goat to eat maximum grass on its path from a[i][j] to a[m-1][n-1]
	// move[i][j]='r' : move right
	// move[i][j]='d' : move down
	
	char move[m][n];
	
	// calculate the solution and max grass to eat using the relation: sum[i][j] = a[i][j] + max(sum[i-1][j],sum[i][j-1])
	
	int i,j;
	for(i=m-1;i>=0;i--){
		for(j=n-1;j>=0;j--){
			
			if(i == m-1 && j == n-1 ){
				sum[i][j] = a[i][j];
			}
			else if(i == m-1 ){
				sum[i][j] = a[i][j] + sum[i][j+1];
				move[i][j]='r';
			}
			else if(j == n-1 ){
				sum[i][j] = a[i][j] + sum[i+1][j];
				move[i][j] = 'd';
			}
			else if(sum[i][j+1]>sum[i+1][j]){
				sum[i][j]= a[i][j] + sum[i][j+1] ;
				move[i][j] = 'r';
			}
			else{
				sum[i][j]= a[i][j] +sum[i+1][j];
				move[i][j]='d';
			}
		}
	}
	
	// Output the best move solution
	
	i=0;
	j=0;
	
	while(i< (m-1) || j< (n-1)){
		printf("\nEat: a[%d][%d]=%d\n",i,j,a[i][j]);
		if(move[i][j]=='r'){
			printf("move right\n");
			j++;
		}
		else{
			printf("move down\n");
			i++;
		}
	}
	
	printf("\nEa: a[%d][%d] = %d\n",i,j,a[i][j]);
	printf("total grass eaten: %d\n",sum[0][0]);
	
	return 0;
}

<pre lang="" line="1" title="CodeMonkey14944" class="run-this">package Directi;


public class DynamicProgramming {

int rows = 0;
int columns = 0;
public static void main(String[] args){
DynamicProgramming dp = new DynamicProgramming();
int[][] array = {{1, 3, 1},{1, 4, 3},{12, 1, 1}};
dp.rows = array.length;
dp.columns = array[0].length;
System.out.println(dp.maximumGrass(0, 0, array));
}
int maximumGrass(int x, int y, int[][] array){
if(x == (rows-1) && y == (columns-1)){
return array[x][y];
} else if( y ==(columns-1)){
return ( maximumGrass(x + 1, y, array) + array[x][y]);
} else if( x == (rows-1)){
return (maximumGrass(x, y + 1, array) + array[x][y]);
} else{
return (Math.max(maximumGrass(x+1, y, array), maximumGrass(x, y+1, array)) + array[x][y]);
}
}

}
</pre>

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define INFINITY 1<<31
struct e
{
int val,i,j;
};
class compare
{
public:
bool operator()(e &x,e &y)
{
if(x.val<y.val)
return true;
return false;
}
};
main()
{
int n;
e temp;
vector<vector<int> > arr2d;
priority_queue<e,vector<e>,compare> q;
cout<<"Enter the matrix size and matrix on which goat will move: ";
cin>>n;
char parent[n][n];int cost[n][n];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++) cost[i][j]=-INFINITY;
arr2d.resize(n);
for(int i=0;i<n;i++) arr2d[i].resize(n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>arr2d[i][j];
cost[0][0]=arr2d[0][0];
temp.val=arr2d[0][0];temp.i=temp.j=0;
q.push(temp);
while(!q.empty())
{
e temp1;
temp=q.top();
q.pop();
if(temp.i+1<n)
{
if(cost[temp.i+1][temp.j]<temp.val+arr2d[temp.i+1][temp.j])
{
cost[temp.i+1][temp.j]=temp.val+arr2d[temp.i+1][temp.j];
parent[temp.i+1][temp.j]='u';
}
temp1.val=cost[temp.i+1][temp.j];temp1.i=temp.i+1;temp1.j=temp.j;
q.push(temp1);
}
if(temp.j+1<n)
{
if(cost[temp.i][temp.j+1]<temp.val+arr2d[temp.i][temp.j+1])
{
cost[temp.i][temp.j+1]=temp.val+arr2d[temp.i][temp.j+1];
parent[temp.i][temp.j+1]='l';
}
temp1.val=cost[temp.i][temp.j+1];temp1.i=temp.i;temp1.j=temp.j+1;
q.push(temp1);
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<parent[i][j]<<" ";
cout<<endl;
}
cout<<endl<<cost[n-1][n-1]<<endl;
}

dp using memoization order mn --> linear in size of matrix

can we apply Dijkstra's Algorithm?

u can keep 2 counts at each cell, one is max(down) , max(right) and
then for cell i,j
right(i,j)= max(right(i-1,j)),right(i,j-1))+cell(i,j)
left(i,j)= max(left(i-1,j)),left(i,j-1))+cell(i,j)

ans=max(left(n,n),right(n,n))

this mayb adhoc approach but it works fine

u can keep 2 counts at each cell, one is max(down) , max(right) and
then for cell i,j
right(i,j)= max(right(i-1,j)),right(i,j-1))+cell(i,j)
down(i,j)= max(down(i-1,j)),down(i,j-1))+cell(i,j)

ans=max(down(n,n),right(n,n))

this mayb adhoc approach but it works fine