最小限の手順ですべてのコインを集めます
隣接して配置された多数のコインの山が与えられます。これらすべてのコインを最小限のステップ数で収集する必要があります。つまり、1 つのステップで 1 つの水平方向のコインまたは垂直方向のコインを収集でき、収集されたコインは連続している必要があります。
例:
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.
この問題は分割統治法を使用して解決できます。下からの水平線を削除することが常に有益であることがわかります。再帰ステップで l インデックスから r インデックスまでのスタックを処理しているとします。毎回、最小の高さを選択して多くの水平線を削除します。その後、スタックは l から最小までと最小 +1 から r までの 2 つの部分に分割され、それらの部分配列で再帰的に呼び出します。もう 1 つは、垂直線を使用してコインを収集することもできるため、(r - l) の垂直線を使用すると常にすべてのコインを収集できるため、再帰呼び出しの結果と (r - l) の間で最小値を選択します。
各サブ配列を呼び出して最小値を見つけるたびに、解の合計時間の計算量は 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>
出力：
4
時間計算量: このアルゴリズムの時間計算量は O(N^2) です。ここで、N は高さ配列の要素の数です。
空間の複雑さ: 高さの配列に対して再帰呼び出しが行われるため、このアルゴリズムの空間複雑さは O(N) です。
