Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0).
Constraints :
- From a cell (i, j) we can move to (i+1, j) or (i, j+1).
- We cannot move from (i, j) if your overall points at (i, j) is <= 0.
- We have to reach at (n-1, m-1) with minimum positive points i.e., > 0
Example
Input: points[m][n] = { {-2, -3, 3},
{-5, -10, 1},
{10, 30, -5}
};
Output: 7
Explanation:
7 is the minimum value to reach destination with
positive throughout the path. Below is the path.
(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)
We start from (0, 0) with 7, we reach(0, 1)
with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)
with and finally we have 1 point (we needed
greater than 0 points at the end).
pasting the code below, please let me know if you found any bug in it.
import java.io.*;
class minInitialDP
{
public static int max(int x, int y)
{
return (x>y?x:y);
}
public static int min(int x, int y)
{
return (x<y?x:y);
}
public static void main(String []args)
{
int points[][] = { {-2, -3, 3},
{-5, -10, 1},
{10, 30, -5}
};
int DP [][] = new int[3][3];
// main code goes here
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if (i==0 && j==0)
{
DP[i][j] = 0;
continue;
}
if( i==0 )
{
if(points[i][j-1] < 0)
{
DP[i][j] = -points[i][j-1]+DP[i][j-1]+1;
}
else
{
DP[i][j] = DP[i][j-1];
}
continue;
}
if(j==0)
{
if(points[i-1][j] < 0)
DP[i][j] = -points[i-1][j]+DP[i-1][j]+1;
else
DP[i][j] = DP[i-1][j];
continue;
}
int pi, pj;
if(points[i][j-1] < 0)
pi = -points[i][j-1]+DP[i][j-1]+1;
else
pi = DP[i][j-1];
if(points[i-1][j] < 0)
pj = -points[i-1][j]+DP[i-1][j]+1;
else
pj = DP[i-1][j];
DP[i][j] = min(pi, pj);
}
}
for(int i=0; i<3; i++)
{
for(int j =0; j<3; j++)
System.out.print(DP[i][j] + " ");
System.out.println("\n");
}
}
}
import java.io.*;
class minInitialDP
{
public static int max(int x, int y)
{
return (x>y?x:y);
}
public static int min(int x, int y)
{
return (x<y?x:y);
}
public static void main(String []args)
{
int points[][] = { {-2, -3, 3},
{-5, -10, 1},
{10, 30, -5}
};
int DP [][] = new int[3][3];
// main code goes here
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if (i==0 && j==0)
{
DP[i][j] = 0;
continue;
}
if( i==0 )
{
if(points[i][j-1] < 0)
{
DP[i][j] = -points[i][j-1]+DP[i][j-1]+1;
}
else
{
DP[i][j] = DP[i][j-1];
}
continue;
}
if(j==0)
{
if(points[i-1][j] < 0)
DP[i][j] = -points[i-1][j]+DP[i-1][j]+1;
else
DP[i][j] = DP[i-1][j];
continue;
}
int pi, pj;
if(points[i][j-1] < 0)
pi = -points[i][j-1]+DP[i][j-1]+1;
else
pi = DP[i][j-1];
if(points[i-1][j] < 0)
pj = -points[i-1][j]+DP[i-1][j]+1;
else
pj = DP[i-1][j];
DP[i][j] = min(pi, pj);
}
}
for(int i=0; i<3; i++)
{
for(int j =0; j<3; j++)
System.out.print(DP[i][j] + " ");
System.out.println("\n");
}
}
}
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeletecan u explain logic behind, and i guess it gives wrong output for
ReplyDeleteint points[][] = {
{-2, -3, -3, 4},
{-5, -10, 1, 5},
{10, 30, -5, 6},
{11, 3, 5, 7},
};
ans is 8, it gives 9