Проблема спаривания друзей


Сложный уровень Легко
Часто спрашивают в Амазонка Expedia GE Healthcare Google Honeywell JP Morgan
Динамическое программирование Модульная арифметика

Постановка задачи

В «Проблема спаривания друзей» указано, что есть N друзей. И каждый из них может оставаться холостым или работать в паре друг с другом. Но как только пара создана, эти два друга не могут участвовать в спаривании. Итак, вам нужно найти общее количество способов, которыми друзья могут быть объединены в пары или они могут остаться одинокими.

Пример

3
4

Проблема спаривания друзей
Подход к проблеме спаривания друзей

Вместо того, чтобы думать об этом как о большой проблеме. Давайте сначала попробуем найти меньшее N. Для N = 1 ответ будет 1. Для N = 2 ответ будет 2. Либо оба друга останутся одинокими, либо они объединятся в пары. При N = 3 третий друг может оставаться холостым. Таким образом, ответ должен быть ответом на проблему с N = 2. Потому что во всех этих случаях наш третий друг может оставаться холостым. А для сопряжения он может выбрать любого из друзей. Итак, выбор 1 друга из N-1 друзей, а затем количество способов, которыми другие могут объединиться / остаться одинокими = (N-1) * F (N-2). Теперь мы можем придумать рекурсивную формулу проблемы.

F(N)     =     F(N-1)   +   (N-1)*F(N-2)
                  ^              ^
                  |              |
Nth friend (stays single) (pairs with N-1 friends)

Из рекурсивная формула, мы видим, что при вычислении F (N) мы вычисляем F (N-2). А затем для F (N-1) мы вычисляем F (N-2). Поэтому вместо пересчета значений мы должны использовать динамическое программирование. Здесь мы можем сохранить все значения F (N) от 0 до N. Но это не требуется. Поскольку значение F (N) зависит только от F (N-1) и F (N-2), это последние 2 значения. Поэтому мы просто продолжим сохранять последние 2 значения. Потому что это сэкономит нам место.

Код:

Код C ++ для проблемы подключения друзей

#include<bits/stdc++.h>
using namespace std;

int main()
{
  // number of friends
  int n;cin>>n;

  int last = 2, lastTolast = 1;
  // here last denotes F(N-1) and lastTolast denotes F(N-2)
  // we can also use a dp array but that will only increase space complexity
  // and from the recursive formula we can see that
  // F(N) is dependent only on F(N-1) and F(N-2)
  int current;
  for(int i=3;i<=n;i++){
    current = last + (i-1)*lastTolast;
    lastTolast = last;
    last = current;
  }
  cout<<current<<endl;
}E
4
10

Код Java для проблемы подключения друзей

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// number of friends

    int last = 2, lastTolast = 1;
    // here last denotes F(N-1) and lastTolast denotes F(N-2)
    // we can also use a dp array but that will only increase space complexity
    // and from the recursive formula we can see that
    // F(N) is dependent only on F(N-1) and F(N-2)
    int current;
    for(int i=3;i<=n;i++){
      current = last + (i-1)*lastTolast;
      lastTolast = last;
      last = current;
    }
    System.out.println(current);
  }
}
4
10

Анализ сложности

Сложность времени

НА), потому что нам нужно запустить цикл до N, чтобы найти его. Поскольку F (N) зависит от F (N-1) и F (N-2).

Космическая сложность

О (1), мы использовали только три переменные для вычислений, и поэтому требуемый интервал был постоянным.