Dadas muchas pilas de monedas que están dispuestas de forma adyacente. Necesitamos recolectar todas estas monedas en el número mínimo de pasos donde en un paso podemos recolectar una línea horizontal de monedas o una línea vertical de monedas y las monedas recolectadas deben ser continuas.
Ejemplos:
Input : height[] = [2 1 2 5 1] Each value of this array corresponds to the height of stack that is we are given five stack of coins, where in first stack 2 coins are there then in second stack 1 coin is there and so on. Output : 4 We can collect all above coins in 4 steps which are shown in below diagram. Each step is shown by different color. First, we have collected last horizontal line of coins after which stacks remains as [1 0 1 4 0] after that, another horizontal line of coins is collected from stack 3 and 4 then a vertical line from stack 4 and at the end a horizontal line from stack 1. Total steps are 4.
Podemos resolver este problema usando el método divide y vencerás. Podemos ver que siempre es beneficioso eliminar las líneas horizontales de abajo. Supongamos que estamos trabajando en pilas del índice l al índice r en un paso de recursión, cada vez que elijamos la altura mínima, eliminaremos esas muchas líneas horizontales después de lo cual la pila se dividirá en dos partes, l al mínimo y mínimo +1 hasta r y llamaremos recursivamente en esos subarreglos. Otra cosa es que también podemos recolectar monedas usando líneas verticales, por lo que elegiremos el mínimo entre el resultado de llamadas recursivas y (r – l) porque usando (r – l) líneas verticales siempre podemos recolectar todas las monedas.
Como cada vez que llamamos a cada subarreglo y encontramos el mínimo de eso, la complejidad temporal total de la solución será O(N 2 )
C++
// C++ program to find minimum number of
// steps to collect stack of coins
#include <bits/stdc++.h>
using namespace std;
// recursive method to collect coins from
// height array l to r, with height h already
// collected
int minStepsRecur(int height[], int l, int r, int h)
{
// if l is more than r, no steps needed
if (l >= r)
return 0;
// loop over heights to get minimum height
// index
int m = l;
for (int i = l; i < r; i++)
if (height[i] < height[m])
m = i;
/* choose minimum from,
1) collecting coins using all vertical
lines (total r - l)
2) collecting coins using lower horizontal
lines and recursively on left and right
segments */
return min(r - l,
minStepsRecur(height, l, m, height[m]) +
minStepsRecur(height, m + 1, r, height[m]) +
height[m] - h);
}
// method returns minimum number of step to
// collect coin from stack, with height in
// height[] array
int minSteps(int height[], int N)
{
return minStepsRecur(height, 0, N, 0);
}
// Driver code to test above methods
int main()
{
int height[] = { 2, 1, 2, 5, 1 };
int N = sizeof(height) / sizeof(int);
cout << minSteps(height, N) << endl;
return 0;
}
Java
// Java Code to Collect all coins in
// minimum number of steps
import java.util.*;
class GFG {
// recursive method to collect coins from
// height array l to r, with height h already
// collected
public static int minStepsRecur(int height[], int l,
int r, int h)
{
// if l is more than r, no steps needed
if (l >= r)
return 0;
// loop over heights to get minimum height
// index
int m = l;
for (int i = l; i < r; i++)
if (height[i] < height[m])
m = i;
/* choose minimum from,
1) collecting coins using all vertical
lines (total r - l)
2) collecting coins using lower horizontal
lines and recursively on left and right
segments */
return Math.min(r - l,
minStepsRecur(height, l, m, height[m]) +
minStepsRecur(height, m + 1, r, height[m]) +
height[m] - h);
}
// method returns minimum number of step to
// collect coin from stack, with height in
// height[] array
public static int minSteps(int height[], int N)
{
return minStepsRecur(height, 0, N, 0);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int height[] = { 2, 1, 2, 5, 1 };
int N = height.length;
System.out.println(minSteps(height, N));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python 3
# Python 3 program to find # minimum number of steps # to collect stack of coins # recursive method to collect # coins from height array l to # r, with height h already # collected def minStepsRecur(height, l, r, h): # if l is more than r, # no steps needed if l >= r: return 0; # loop over heights to # get minimum height index m = l for i in range(l, r): if height[i] < height[m]: m = i # choose minimum from, # 1) collecting coins using # all vertical lines (total r - l) # 2) collecting coins using # lower horizontal lines and # recursively on left and # right segments return min(r - l, minStepsRecur(height, l, m, height[m]) + minStepsRecur(height, m + 1, r, height[m]) + height[m] - h) # method returns minimum number # of step to collect coin from # stack, with height in height[] array def minSteps(height, N): return minStepsRecur(height, 0, N, 0) # Driver code height = [ 2, 1, 2, 5, 1 ] N = len(height) print(minSteps(height, N)) # This code is contributed # by ChitraNayal
C#
// C# Code to Collect all coins in
// minimum number of steps
using System;
class GFG {
// recursive method to collect coins from
// height array l to r, with height h already
// collected
public static int minStepsRecur(int[] height, int l,
int r, int h)
{
// if l is more than r, no steps needed
if (l >= r)
return 0;
// loop over heights to
// get minimum height index
int m = l;
for (int i = l; i < r; i++)
if (height[i] < height[m])
m = i;
/* choose minimum from,
1) collecting coins using all vertical
lines (total r - l)
2) collecting coins using lower horizontal
lines and recursively on left and right
segments */
return Math.Min(r - l,
minStepsRecur(height, l, m, height[m]) +
minStepsRecur(height, m + 1, r, height[m]) +
height[m] - h);
}
// method returns minimum number of step to
// collect coin from stack, with height in
// height[] array
public static int minSteps(int[] height, int N)
{
return minStepsRecur(height, 0, N, 0);
}
/* Driver program to test above function */
public static void Main()
{
int[] height = { 2, 1, 2, 5, 1 };
int N = height.Length;
Console.Write(minSteps(height, N));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to find minimum number of
// steps to collect stack of coins
// recursive method to collect
// coins from height array l to
// r, with height h already
// collected
function minStepsRecur($height, $l,
$r, $h)
{
// if l is more than r,
// no steps needed
if ($l >= $r)
return 0;
// loop over heights to
// get minimum height
// index
$m = $l;
for ($i = $l; $i < $r; $i++)
if ($height[$i] < $height[$m])
$m = $i;
/* choose minimum from,
1) collecting coins using
all vertical lines
(total r - l)
2) collecting coins using
lower horizontal lines
and recursively on left
and right segments */
return min($r - $l,
minStepsRecur($height, $l, $m, $height[$m]) +
minStepsRecur($height, $m + 1, $r, $height[$m]) +
$height[$m] - $h);
}
// method returns minimum number of step to
// collect coin from stack, with height in
// height[] array
function minSteps($height, $N)
{
return minStepsRecur($height, 0, $N, 0);
}
// Driver Code
$height = array(2, 1, 2, 5, 1);
$N = sizeof($height);
echo minSteps($height, $N) ;
// This code is contributed by nitin mittal.
?>
Javascript
<script>
// Javascript Code to Collect all coins in
// minimum number of steps
// recursive method to collect coins from
// height array l to r, with height h already
// collected
function minStepsRecur(height,l,r,h)
{
// if l is more than r, no steps needed
if (l >= r)
return 0;
// loop over heights to get minimum height
// index
let m = l;
for (let i = l; i < r; i++)
if (height[i] < height[m])
m = i;
/* choose minimum from,
1) collecting coins using all vertical
lines (total r - l)
2) collecting coins using lower horizontal
lines and recursively on left and right
segments */
return Math.min(r - l,
minStepsRecur(height, l, m, height[m]) +
minStepsRecur(height, m + 1, r, height[m]) +
height[m] - h);
}
// method returns minimum number of step to
// collect coin from stack, with height in
// height[] array
function minSteps(height,N)
{
return minStepsRecur(height, 0, N, 0);
}
/* Driver program to test above function */
let height=[2, 1, 2, 5, 1 ];
let N = height.length;
document.write(minSteps(height, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
4
Este artículo es una contribución de Utkarsh Trivedi . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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