Minimum Initial Points to Reach Destination
Last Updated :
23 Nov, 2023
Given a M*N grid with each cell consisting of positive, negative, or no points i.e., zero points. From a cell (i, j) we can move to (i+1, j) or (i, j+1) and we can move to a cell only if we have positive points ( > 0 ) when we move to that cell. 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).
Example:
Input: M = 3, N = 3, points[][] = {{-2,-3,3}, {-5,-10,1}, {10,30,-5}}
Output: 7
Explanation: 7 is the minimum value to reach the 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).
Input: M = 3, N = 2, points[][] = {{2,3}, {5,10}, {10,30}}
Output: 1
Explanation: Take any path, all of them are positive. So, required one point at the start
Minimum Initial Points to Reach Destination using Dynamic Programming:
We can solve this problem through bottom-up table filling dynamic programming technique.
The idea is to use a 2D dp array where dp[i][j] represents the minimum initial points required to reach destination cell (m-1,n-1) starting from cell (i,j). From any cell (i,j) there two options to move (i+1,j) and (i,j+1), so to compute dp[i][j], we choose a cell that require less intial points to reach the end i.e., min(dp[i+1][j], dp[i][j+1]).
Follow the steps to solve the problem
- Create a 2D dp array of the same size as the grid, where dp[i][j] represents the minimum initial points required to reach destination cell (m-1,n-1) starting from cell (i,j). dp[0][0] is our final answer.
- Start filling the array from the bottom right corner to left top.
- At any cell (i,j) there two options to move (i+1,j) and (i,j+1). We choose a cell that require less intial points to reach the end i.e., min_Points_on_exit = min(dp[i+1][j], dp[i][j+1]) min(dp[i+1][j], dp[i][j+1]). From min_Points_on_exit we can compute dp[i][j] by:-
dp[i][j] = max(min_Points_on_exit – points[i][j], 1)
How the above expression covers all the cases?
- If points[i][j] == 0, then nothing is gained in this cell;we leave the cell with the same points as we enter the cell with, i.e. dp[i][j] = min_Points_on_exit.
- If points[i][j] < 0, then the we must have points greater than min_Points_on_exit before entering (i, j) in order to compensate for the points lost in this cell. The minimum amount of compensation is ” – points[i][j] “, so we have dp[i][j] = min_Points_on_exit – points[i][j].
- If points[i][j] > 0, then we could enter (i, j) with points as little as min_Points_on_exit – points[i][j]. since we could gain “points[i][j]” points in this cell. However, the value of min_Points_on_exit – points[i][j] might drop to 0 or below in this situation. When this happens, we must increase the value to 1 in order to make sure dp[i][j] stays positive: dp[i][j] = max(min_Points_on_exit – points[i][j], 1).
Below is the implementation of above algorithm.
C++14
#include <bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
int minInitialPoints(int points[][C])
{
int dp[R][C];
int m = R, n = C;
dp[m - 1][n - 1] = points[m - 1][n - 1] > 0
? 1
: abs(points[m - 1][n - 1]) + 1;
for (int i = m - 2; i >= 0; i--)
dp[i][n - 1]
= max(dp[i + 1][n - 1] - points[i][n - 1], 1);
for (int j = n - 2; j >= 0; j--)
dp[m - 1][j]
= max(dp[m - 1][j + 1] - points[m - 1][j], 1);
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int min_points_on_exit
= min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j]
= max(min_points_on_exit - points[i][j], 1);
}
}
return dp[0][0];
}
int main()
{
int points[R][C]
= { { -2, -3, 3 }, { -5, -10, 1 }, { 10, 30, -5 } };
cout << "Minimum Initial Points Required: "
<< minInitialPoints(points);
return 0;
}
|
Java
import java.io.*;
import java.util.*;
class min_steps {
static int minInitialPoints(int points[][], int R,
int C)
{
int dp[][] = new int[R][C];
int m = R, n = C;
dp[m - 1][n - 1]
= points[m - 1][n - 1] > 0
? 1
: Math.abs(points[m - 1][n - 1]) + 1;
for (int i = m - 2; i >= 0; i--)
dp[i][n - 1] = Math.max(
dp[i + 1][n - 1] - points[i][n - 1], 1);
for (int j = n - 2; j >= 0; j--)
dp[m - 1][j] = Math.max(
dp[m - 1][j + 1] - points[m - 1][j], 1);
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int min_points_on_exit
= Math.min(dp[i + 1][j], dp[i][j + 1]);
dp[i][j] = Math.max(
min_points_on_exit - points[i][j], 1);
}
}
return dp[0][0];
}
public static void main(String args[])
{
int points[][] = { { -2, -3, 3 },
{ -5, -10, 1 },
{ 10, 30, -5 } };
int R = 3, C = 3;
System.out.println(
"Minimum Initial Points Required: "
+ minInitialPoints(points, R, C));
}
}
|
Python3
import math as mt
R = 3
C = 3
def minInitialPoints(points):
dp = [[0 for x in range(C + 1)]
for y in range(R + 1)]
m, n = R, C
if points[m - 1][n - 1] > 0:
dp[m - 1][n - 1] = 1
else:
dp[m - 1][n - 1] = abs(points[m - 1][n - 1]) + 1
for i in range(m - 2, -1, -1):
dp[i][n - 1] = max(dp[i + 1][n - 1] -
points[i][n - 1], 1)
for i in range(n - 2, -1, -1):
dp[m - 1][i] = max(dp[m - 1][i + 1] -
points[m - 1][i], 1)
for i in range(m - 2, -1, -1):
for j in range(n - 2, -1, -1):
min_points_on_exit = min(dp[i + 1][j],
dp[i][j + 1])
dp[i][j] = max(min_points_on_exit -
points[i][j], 1)
return dp[0][0]
points = [[-2, -3, 3],
[-5, -10, 1],
[10, 30, -5]]
print("Minimum Initial Points Required:",
minInitialPoints(points))
|
C#
using System;
class GFG {
static int minInitialPoints(int[, ] points, int R,
int C)
{
int[, ] dp = new int[R, C];
int m = R, n = C;
dp[m - 1, n - 1]
= points[m - 1, n - 1] > 0
? 1
: Math.Abs(points[m - 1, n - 1]) + 1;
for (int i = m - 2; i >= 0; i--)
dp[i, n - 1] = Math.Max(
dp[i + 1, n - 1] - points[i, n - 1], 1);
for (int j = n - 2; j >= 0; j--)
dp[m - 1, j] = Math.Max(
dp[m - 1, j + 1] - points[m - 1, j], 1);
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int min_points_on_exit
= Math.Min(dp[i + 1, j], dp[i, j + 1]);
dp[i, j] = Math.Max(
min_points_on_exit - points[i, j], 1);
}
}
return dp[0, 0];
}
public static void Main()
{
int[, ] points = { { -2, -3, 3 },
{ -5, -10, 1 },
{ 10, 30, -5 } };
int R = 3, C = 3;
Console.Write("Minimum Initial Points Required: "
+ minInitialPoints(points, R, C));
}
}
|
Javascript
<script>
function minInitialPoints(points,R,C)
{
var dp = new Array(R);
var m = R, n = C;
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(C);
}
dp[m-1][n-1] = points[m-1][n-1] > 0? 1: Math.abs(points[m-1][n-1]) + 1;
for (var i = m-2; i >= 0; i--)
dp[i][n-1] = Math.max(dp[i+1][n-1] - points[i][n-1], 1);
for (var j = n-2; j >= 0; j--)
dp[m-1][j] = Math.max(dp[m-1][j+1] - points[m-1][j], 1);
for (var i=m-2; i>=0; i--)
{
for (var j=n-2; j>=0; j--)
{
var min_points_on_exit = Math.min(dp[i+1][j], dp[i][j+1]);
dp[i][j] = Math.max(min_points_on_exit - points[i][j], 1);
}
}
return dp[0][0];
}
var points = [ [-2,-3,3],
[-5,-10,1],
[10,30,-5]
];
var R = 3,C = 3;
document.write("Minimum Initial Points Required: "+minInitialPoints(points,R,C) );
</script>
|
PHP
<?php
$R = 3;
$C = 3;
function minInitialPoints($points)
{
global $R;
global $C;
$dp[$R][$C] = array();
$m = $R;
$n = $C;
$dp[$m - 1][$n - 1] = $points[$m - 1][$n - 1] > 0 ? 1 :
abs($points[$m - 1][$n - 1]) + 1;
for ($i = $m - 2; $i >= 0; $i--)
$dp[$i][$n - 1] = max($dp[$i + 1][$n - 1] -
$points[$i][$n - 1], 1);
for ($j = $n - 2; $j >= 0; $j--)
$dp[$m - 1][$j] = max($dp[$m - 1][$j + 1] -
$points[$m - 1][$j], 1);
for ($i = $m - 2; $i >= 0; $i--)
{
for ($j = $n - 2; $j >= 0; $j--)
{
$min_points_on_exit = min($dp[$i + 1][$j],
$dp[$i][$j + 1]);
$dp[$i][$j] = max($min_points_on_exit -
$points[$i][$j], 1);
}
}
return $dp[0][0];
}
$points = array(array(-2, -3, 3),
array(-5, -10, 1),
array(10, 30, -5));
echo "Minimum Initial Points Required: ",
minInitialPoints($points);
?>
|
Output
Minimum Initial Points Required: 7
Time Complexity: O(M*N)
Auxiliary Space: O(M*N)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...