최소한의 단계로 모든 코인을 수집하세요

인접하게 배열된 많은 동전 더미가 주어졌습니다. 우리는 한 단계에서 하나의 수평 라인 또는 수직 라인의 코인을 수집할 수 있는 최소 단계 수로 이러한 모든 코인을 수집해야 하며 수집된 코인은 연속되어야 합니다.
예:

  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.

아토이 c

분할 정복 방법을 사용하여 이 문제를 해결할 수 있습니다. 아래에서 수평선을 제거하는 것이 항상 유익하다는 것을 알 수 있습니다. 재귀 단계에서 l 인덱스에서 r 인덱스까지의 스택 작업을 한다고 가정합니다. 최소 높이를 선택할 때마다 많은 수평선을 제거한 후 스택은 l에서 최소, 최소 +1에서 r까지 두 부분으로 나뉘고 해당 하위 배열에서 재귀적으로 호출합니다. 또 다른 점은 수직선을 사용하여 동전을 수집할 수도 있으므로 (r - l) 수직선을 사용하면 항상 모든 동전을 수집할 수 있기 때문에 재귀 호출 결과와 (r - l) 사이에서 최소값을 선택한다는 것입니다.
매번 각 하위 배열을 호출하고 솔루션의 총 시간 복잡도의 최소값을 찾는 것은 O(N²)

C++

// 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# 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(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>

산출:

시간 복잡도: 이 알고리즘의 시간 복잡도는 O(N^2)입니다. 여기서 N은 높이 배열의 요소 수입니다.

공간 복잡도: 이 알고리즘의 공간 복잡도는 높이 배열에 대한 재귀 호출로 인해 O(N)입니다.

퀴즈 만들기