Pozbierajte všetky mince v minimálnom počte krokov
Vzhľadom na veľa hromád mincí, ktoré sú usporiadané vedľa seba. Všetky tieto mince musíme nazbierať v minimálnom počte krokov, pričom v jednom kroku môžeme nazbierať jednu horizontálnu líniu mincí alebo vertikálnu líniu mincí a zbierané mince by mali byť súvislé.
Príklady:
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.
Tento problém môžeme vyriešiť pomocou metódy rozdeľ a panuj. Vidíme, že je vždy prospešné odstrániť vodorovné čiary zospodu. Predpokladajme, že pracujeme na zásobníkoch od indexu l po index r v rekurznom kroku zakaždým, keď zvolíme minimálnu výšku, odstránime tých veľa vodorovných čiar, po ktorých sa zásobník rozdelí na dve časti l na minimum a minimum +1 až r a budeme volať rekurzívne v týchto podpoliach. Ďalšia vec je, že mince môžeme zbierať aj pomocou zvislých čiar, takže budeme voliť minimum medzi výsledkom rekurzívnych hovorov a (r - l), pretože pomocou (r - l) zvislých čiar môžeme vždy pozbierať všetky mince.
Ako zakaždým voláme každé podpole a nájdenie minimálnej celkovej časovej zložitosti riešenia bude O(N 2 )
// C++ program to find minimum number of // steps to collect stack of coins #include 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 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>
výstup:
4
Časová zložitosť: Časová zložitosť tohto algoritmu je O(N^2), kde N je počet prvkov v poli výšok.
Zložitosť priestoru: Priestorová zložitosť tohto algoritmu je O(N) v dôsledku rekurzívnych volaní, ktoré sa uskutočňujú na poli výšok.
