友達のペアリングの問題


難易度 簡単に
よく聞かれる Amazon (アマゾン) エクスペディア GEヘルスケア Google ハニーウェル JPモルガン
動的計画法 モジュラー演算

問題文

「友達ペアリング問題」は、N人の友達がいると述べています。 そして、それらはそれぞれ単一のままにすることも、互いにペアにすることもできます。 しかし、ペアが作られると、それらのXNUMX人の友人はペアリングに参加できなくなります。 したがって、友達をペアにする方法、または友達をXNUMX人のままにする方法の総数を見つける必要があります。A

3
4

友達のペアリングの問題
友達ペアリング問題へのアプローチ

それを大きな問題として考える代わりに。 まず、小さいNを解いてみましょう。N= 1の場合、答えは1です。N= 2の場合、答えは2です。両方の友達が3人のままであるか、ペアになっています。 N = 2の場合、1番目の友人はどちらも独身のままでいられます。 したがって、その答えはN = 1の問題に対する答えである必要があります。これらすべての場合において、私たちの1番目の友人は独身のままでいることができます。 また、ペアリングの場合は、友達のいずれかを選択できます。 したがって、N-2人の友人からXNUMX人の友人を選択し、次に他の人がペアリング/シングル滞在できる方法の数=(N-XNUMX)* F(N-XNUMX)。 これで、問題の再帰式を考えることができます。

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)を計算します。 したがって、値を再計算する代わりに、 動的計画法。 ここでは、0からNまでのF(N)値全体を格納できます。ただし、これは必須ではありません。 F(N)の値は、最後の1つの値であるF(N-2)とF(N-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)に依存しているためです。

スペースの複雑さ

O(1)、 計算にはXNUMXつの変数のみを使用したため、必要な間隔は一定でした。