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


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

Постановка проблеми  

У “Проблемі сполучення друзів” зазначається, що є N друзів. І кожен з них може залишатися одиноким або бути в парі між собою. Але як тільки пара складена, ці двоє друзів не можуть брати участь у спарюванні. Отже, вам потрібно знайти загальну кількість способів, за допомогою яких друзі можуть скласти пари або вони можуть залишитися самотніми

Приклад  

3
4

Проблема сполучення друзівPin
Підхід для друзів Проблема сполучення  

Замість того, щоб думати про це як про велику проблему. Давайте спершу спробуємо розв’язати для меншої 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

Аналіз складності  

Складність часу

O (N), тому що нам потрібно запустити цикл до N, щоб знайти його. Оскільки F (N) залежить від F (N-1) та F (N-2).

Складність простору

O (1), ми використовували лише три змінні для обчислення, і, отже, необхідний інтервал був постійним.