Dada una cuadrícula en la que cada celda consta de puntos positivos, negativos o sin puntos, es decir, cero puntos. Podemos movernos a través de una celda solo si tenemos puntos positivos ( > 0 ). Cada vez que pasamos por una celda, los puntos en esa celda se agregan a nuestros puntos generales. Necesitamos encontrar puntos iniciales mínimos para llegar a la celda (m-1, n-1) desde (0, 0).
Restricciones:
- Desde una celda (i, j) podemos pasar a (i+1, j) o (i, j+1).
- No podemos movernos de (i, j) si sus puntos generales en (i, j) son <= 0.
- Tenemos que llegar a (n-1, m-1) con un mínimo de puntos positivos, es decir, > 0.
Ejemplo:
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).
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
A primera vista, este problema parece similar a Max/Min Cost Path , pero los puntos totales máximos obtenidos no garantizarán los puntos iniciales mínimos. Además, es obligatorio en el problema actual que los puntos nunca caigan a cero o menos. Por ejemplo, supongamos que existen dos rutas desde la celda de origen a la de destino.
Podemos resolver este problema a través de la técnica de programación dinámica de llenado de tablas de abajo hacia arriba.
- Para empezar, debemos mantener un arreglo 2D dp del mismo tamaño que la cuadrícula, donde dp[i][j] representa los puntos mínimos que garantizan la continuación del viaje hasta el destino antes de ingresar a la celda (i, j). Es obvio que dp[0][0] es nuestra solución final. Por lo tanto, para este problema, necesitamos llenar la tabla desde la esquina inferior derecha hasta la esquina superior izquierda.
- Ahora, decidamos los puntos mínimos necesarios para salir de la celda (i, j) (recuerde que nos estamos moviendo de abajo hacia arriba). Solo hay dos caminos para elegir: (i+1, j) y (i, j+1). Por supuesto, elegiremos la celda en la que el jugador puede terminar el resto de su viaje con menos puntos iniciales. Por lo tanto tenemos: min_Points_on_exit = min(dp[i+1][j], dp[i][j+1])
Ahora sabemos cómo calcular min_Points_on_exit, pero necesitamos llenar la tabla dp[][] para obtener la solución en dp[0][0].
¿Cómo calcular dp[i][j]?
El valor de dp[i][j] se puede escribir de la siguiente manera.
- dp[i][j] = max(min_Points_on_exit – puntos[i][j], 1)
Veamos cómo la expresión anterior cubre todos los casos.
- Si puntos[i][j] == 0, entonces no se gana nada en esta celda; el jugador puede salir de la celda con los mismos puntos con los que entra en la habitación, es decir, dp[i][j] = min_Points_on_exit.
- Si puntos[i][j] < 0, entonces el jugador debe tener puntos mayores que min_Points_on_exit antes de ingresar (i, j) para compensar los puntos perdidos en esta celda. La cantidad mínima de compensación es ” – puntos[i][j] “, por lo que tenemos dp[i][j] = min_Points_on_exit – puntos[i][j].
- Si los puntos[i][j] > 0, entonces el jugador podría ingresar (i, j) con puntos tan pequeños como min_Points_on_exit – puntos[i][j]. ya que podría ganar «puntos [i] [j]» puntos en esta celda. Sin embargo, el valor de min_Points_on_exit – points[i][j] podría caer a 0 o menos en esta situación. Cuando esto sucede, debemos recortar el valor a 1 para asegurarnos de que dp[i][j] permanezca positivo: dp[i][j] = max(min_Points_on_exit – points[i][j], 1).
Finalmente devuelve dp[0][0] que es nuestra respuesta.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program to find minimum initial points to reach destination
#include<bits/stdc++.h>
#define R 3
#define C 3
using namespace std;
int minInitialPoints(int points[][C])
{
// dp[i][j] represents the minimum initial points player
// should have so that when starts with cell(i, j) successfully
// reaches the destination cell(m-1, n-1)
int dp[R][C];
int m = R, n = C;
// Base case
dp[m-1][n-1] = points[m-1][n-1] > 0? 1:
abs(points[m-1][n-1]) + 1;
// Fill last row and last column as base to fill
// entire table
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);
// fill the table in bottom-up fashion
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];
}
// Driver Program
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
class min_steps
{
static int minInitialPoints(int points[][],int R,int C)
{
// dp[i][j] represents the minimum initial points player
// should have so that when starts with cell(i, j) successfully
// reaches the destination cell(m-1, n-1)
int dp[][] = new int[R][C];
int m = R, n = C;
// Base case
dp[m-1][n-1] = points[m-1][n-1] > 0? 1:
Math.abs(points[m-1][n-1]) + 1;
// Fill last row and last column as base to fill
// entire table
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);
// fill the table in bottom-up fashion
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];
}
/* Driver program to test above function */
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) );
}
}/* This code is contributed by Rajat Mishra */
Python3
# Python3 program to find minimum initial
# points to reach destination
import math as mt
R = 3
C = 3
def minInitialPoints(points):
'''
dp[i][j] represents the minimum initial
points player should have so that when
starts with cell(i, j) successfully
reaches the destination cell(m-1, n-1)
'''
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
'''
Fill last row and last column as base
to fill entire table
'''
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 (2, -1, -1):
dp[m - 1][i] = max(dp[m - 1][i + 1] -
points[m - 1][i], 1)
'''
fill the table in bottom-up fashion
'''
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]
# Driver code
points = [[-2, -3, 3],
[-5, -10, 1],
[10, 30, -5]]
print("Minimum Initial Points Required:",
minInitialPoints(points))
# This code is contributed by
# Mohit kumar 29 (IIIT gwalior)
C#
// C# program Minimum Initial Points
// to Reach Destination
using System;
class GFG {
static int minInitialPoints(int [,]points,
int R, int C)
{
// dp[i][j] represents the
// minimum initial points
// player should have so
// that when starts with
// cell(i, j) successfully
// reaches the destination
// cell(m-1, n-1)
int [,]dp = new int[R,C];
int m = R, n = C;
// Base case
dp[m - 1,n - 1] = points[m - 1, n - 1] > 0 ? 1:
Math.Abs(points[m - 1,n - 1]) + 1;
// Fill last row and last
// column as base to fill
// entire table
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);
// fill the table in
// bottom-up fashion
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];
}
// Driver Code
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));
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// Javascript program to find minimum initial points to reach destination
function minInitialPoints(points,R,C)
{
// dp[i][j] represents the minimum initial points player
// should have so that when starts with cell(i, j) successfully
// reaches the destination cell(m-1, n-1)
var dp = new Array(R);
var m = R, n = C;
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(C);
}
// Base case
dp[m-1][n-1] = points[m-1][n-1] > 0? 1: Math.abs(points[m-1][n-1]) + 1;
// Fill last row and last column as base to fill
// entire table
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);
// fill the table in bottom-up fashion
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) );
//This code is contributed by shruti456rawal
</script>
PHP
<?php
// PHP program to find minimum initial
// points to reach destination
$R = 3;
$C = 3;
function minInitialPoints($points)
{
// dp[i][j] represents the minimum
// initial points player should have
// so that when starts with cell(i, j)
// successfully reaches the destination
// cell(m-1, n-1)
global $R;
global $C;
$dp[$R][$C] = array();
$m = $R;
$n = $C;
// Base case
$dp[$m - 1][$n - 1] = $points[$m - 1][$n - 1] > 0 ? 1 :
abs($points[$m - 1][$n - 1]) + 1;
// Fill last row and last column as
// base to fill entire table
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);
// fill the table in bottom-up fashion
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];
}
// Driver Code
$points = array(array(-2, -3, 3),
array(-5, -10, 1),
array(10, 30, -5));
echo "Minimum Initial Points Required: ",
minInitialPoints($points);
// This code is contributed by akt_mit
?>
Producción
Minimum Initial Points Required: 7
Complejidad de Tiempo : O(R*C)
Espacio Auxiliar : O(R*C)
Este artículo es una contribución de Gaurav Ahirwar. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA