Рубрики

Соберите все монеты за минимальное количество шагов

Дано много стопок монет, которые расположены рядом. Нам нужно собрать все эти монеты за минимальное количество шагов, где за один шаг мы можем собрать одну горизонтальную линию монет или вертикальную линию монет, и собранные монеты должны быть непрерывными.

Примеры :

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 index до r index на шаге рекурсии, каждый раз, когда мы будем выбирать минимальную высоту, удаляем те много горизонтальных линий, после которых стек будет разбит на две части, от l до минимума и от +1 до r и мы будем вызывать рекурсивно в этих подмассивах. Другое дело, что мы также можем собирать монеты, используя вертикальные линии, поэтому мы выберем минимум между результатом рекурсивных вызовов и (r — l), потому что, используя (r — l) вертикальные линии, мы всегда можем собрать все монеты.
Поскольку каждый раз, когда мы вызываем каждый подмассив и находим минимум этого, общая временная сложность решения будет O (N 2 )

C ++

// C ++ программа для поиска минимального количества
// шаги, чтобы собрать стопку монет
#include <bits/stdc++.h>

using namespace std;

  
// рекурсивный метод сбора монет из
// массив высот от l до r, уже с высотой h
// собрал

int minStepsRecur(int height[], int l, int r, int h)

{

    // если l больше чем r, никаких шагов не требуется

    if (l >= r)

        return 0;

  

    // цикл по высоте, чтобы получить минимальную высоту

    // показатель

    int m = l;

    for (int i = l; i < r; i++)

        if (height[i] < height[m])

            m = i;

  

    / * выберите минимум из,

        1) собирать монеты используя все вертикали

        линии (всего г - л)

        2) собирать монеты используя нижнюю горизонталь

        линии и рекурсивно слева и справа

        сегменты * /

    return min(r - l,

               minStepsRecur(height, l, m, height[m]) + 

               minStepsRecur(height, m + 1, r, height[m]) + 

               height[m] - h);

}

  
// метод возвращает минимальное количество шагов в
// собираем монету из стопки, высотой в
// массив высоты []

int minSteps(int height[], int N)

{

    return minStepsRecur(height, 0, N, 0);

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int height[] = { 2, 1, 2, 5, 1 };

    int N = sizeof(height) / sizeof(int);

  

    cout << minSteps(height, N) << endl;

    return 0;

}

Джава

// Java-код для сбора всех монет в
// минимальное количество шагов

import java.util.*;

  

class GFG {

  

    // рекурсивный метод сбора монет из

    // массив высот от l до r, уже с высотой h

    // собрал

    public static int minStepsRecur(int height[], int l,

                                           int r, int h)

    {

        // если l больше чем r, никаких шагов не требуется

        if (l >= r)

            return 0;

  

        // цикл по высоте, чтобы получить минимальную высоту

        // показатель

        int m = l;

        for (int i = l; i < r; i++)

            if (height[i] < height[m])

                m = i;

  

        / * выберите минимум из,

            1) собирать монеты используя все вертикали

            линии (всего г - л)

            2) собирать монеты используя нижнюю горизонталь

            линии и рекурсивно слева и справа

            сегменты * /

        return Math.min(r - l,

                        minStepsRecur(height, l, m, height[m]) + 

                        minStepsRecur(height, m + 1, r, height[m]) +

                        height[m] - h);

    }

  

    // метод возвращает минимальное количество шагов в

    // собираем монету из стопки, высотой в

    // массив высоты []

    public static int minSteps(int height[], int N)

    {

        return minStepsRecur(height, 0, N, 0);

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args)

    {

  

        int height[] = { 2, 1, 2, 5, 1 };

        int N = height.length;

  

        System.out.println(minSteps(height, N));

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

Python 3

# Python 3 программа для поиска
# минимальное количество шагов
# собрать стопку монет

  
# рекурсивный метод для сбора
# монеты из массива высот от l до
# r, уже с высотой h
# собрал

def minStepsRecur(height, l, r, h):

  

    # если l больше чем r,

    # никаких шагов не требуется

    if l >= r:

        return 0;

  

    # цикл по высоте, чтобы

    # получить индекс минимальной высоты

    m = l

    for i in range(l, r):

        if height[i] < height[m]:

            m = i

  

    # выберите минимум из,

    # 1) сбор монет с использованием

    # все вертикальные линии (всего r - l)

    # 2) сбор монет с использованием

    # нижние горизонтальные линии и

    # рекурсивно слева и

    # правые сегменты

    return min(r - l,

            minStepsRecur(height, l, m, height[m]) +

            minStepsRecur(height, m + 1, r, height[m]) +

            height[m] - h)

  
# метод возвращает минимальное число
№ шага для сбора монеты из
# стек, с высотой в массиве []

def minSteps(height, N):

    return minStepsRecur(height, 0, N, 0)

  
# Код драйвера

height = [ 2, 1, 2, 5, 1 ]

N = len(height)

print(minSteps(height, N))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # код для сбора всех монет в
// минимальное количество шагов

using System;

  

class GFG {

  

    // рекурсивный метод сбора монет из

    // массив высот от l до r, уже с высотой h

    // собрал

    public static int minStepsRecur(int[] height, int l,

                                           int r, int h)

    {

        // если l больше чем r, никаких шагов не требуется

        if (l >= r)

            return 0;

  

        // перебрать высоту

        // получаем индекс минимальной высоты

        int m = l;

        for (int i = l; i < r; i++)

            if (height[i] < height[m])

                m = i;

  

        / * выберите минимум из,

            1) собирать монеты используя все вертикали

            линии (всего г - л)

            2) собирать монеты используя нижнюю горизонталь

            линии и рекурсивно слева и справа

            сегменты * /

        return Math.Min(r - l,

                        minStepsRecur(height, l, m, height[m]) + 

                        minStepsRecur(height, m + 1, r, height[m]) +

                        height[m] - h);

    }

  

    // метод возвращает минимальное количество шагов в

    // собираем монету из стопки, высотой в

    // массив высоты []

    public static int minSteps(int[] height, int N)

    {

        return minStepsRecur(height, 0, N, 0);

    }

  

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void Main()

    {

        int[] height = { 2, 1, 2, 5, 1 };

        int N = height.Length;

  

        Console.Write(minSteps(height, N));

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// PHP программа для поиска минимального количества
// шаги, чтобы собрать стопку монет

  
// рекурсивный метод для сбора
// монеты из массива высот l в
// г, с высотой h уже
// собрал

function minStepsRecur($height, $l,

                            $r, $h)

{

      

    // если l больше чем r,

    // никаких шагов не требуется

    if ($l >= $r)

        return 0;

  

    // перебрать высоту

    // получаем минимальную высоту

    // показатель

    $m = $l;

    for ($i = $l; $i < $r; $i++)

        if ($height[$i] < $height[$m])

            $m = $i;

  

    / * выберите минимум из,

        1) сбор монет с использованием

           все вертикальные линии

           (всего г - л)

        2) собирать монеты, используя

           нижние горизонтальные линии

           и рекурсивно слева

           и правые сегменты * /

    return min($r - $l,

           minStepsRecur($height, $l, $m, $height[$m]) + 

           minStepsRecur($height, $m + 1, $r, $height[$m]) + 

           $height[$m] - $h);

}

  
// метод возвращает минимальное количество шагов в
// собираем монету из стопки, высотой в
// массив высоты []

function minSteps($height, $N)

{

    return minStepsRecur($height, 0, $N, 0);

}

  

    // Код драйвера

    $height = array(2, 1, 2, 5, 1);

    $N = sizeof($height);

  

    echo minSteps($height, $N) ;

      
// Этот код предоставлен нитин митталь.
?>


Выход:

4

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Соберите все монеты за минимальное количество шагов

0.00 (0%) 0 votes