Date molte pile di monete disposte adiacenti. Dobbiamo raccogliere tutte queste monete nel numero minimo di passaggi in cui in un passaggio possiamo raccogliere una linea orizzontale di monete o una linea verticale di monete e le monete raccolte dovrebbero essere continue.
Esempi:
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.
incapsulamento Java
Possiamo risolvere questo problema usando il metodo divide et impera. Possiamo vedere che è sempre utile rimuovere le linee orizzontali dal basso. Supponiamo di lavorare su stack dall'indice l all'indice r in un passaggio di ricorsione ogni volta che sceglieremo l'altezza minima rimuovere quelle molte linee orizzontali dopo le quali lo stack verrà suddiviso in due parti da l al minimo e dal minimo +1 fino a r e chiameremo ricorsivamente in quei sottoarray. Un'altra cosa è che possiamo anche raccogliere monete usando le linee verticali, quindi sceglieremo il minimo tra il risultato delle chiamate ricorsive e (r - l) perché usando le linee verticali (r - l) possiamo sempre raccogliere tutte le monete.
Poiché ogni volta che chiamiamo ciascun sottoarray e troviamo il minimo della complessità temporale totale della soluzione sarà O(N2)
C++
// C++ program to find minimum number of // steps to collect stack of coins #include
// 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 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# 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 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. ?> <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(heightlrh) { // 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(heightN) { 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>
Produzione:
4
Complessità temporale: La complessità temporale di questo algoritmo è O(N^2) dove N è il numero di elementi nella matrice di altezze.
Complessità spaziale: La complessità spaziale di questo algoritmo è O(N) a causa delle chiamate ricorsive effettuate sull'array di altezze.