朋友配对问题(Friends Pairing Problem)--动态规划

给定n个朋友，每个人可以单身，也可以与其他朋友配对。 每个朋友只能配对一次。 找出朋友保持单身或配对的方法的总数。
例如当n = 3,既有3个朋友，此时共有四种方式
{1}，{2}，{3} 全部是单身
{1}，{2，3} 1是单身，2和3配对
{1，2}，{3} 1和2配对，3单身
{1，3}，{2} 1和3配对，2单身
那么该如何解决这个问题呢
假设f（n）等于n个人单身或者配对的总数目。
对于第n个人，有两种选择
1）第n个人单身，我们回到f（n - 1）。
2）第n个人和剩余的n - 1个人任意配对，共有(n - 1)* f (n - 2)种。
因此f(n)可以递归的表示为f(n) = f(n - 1) + (n - 1)* f(n - 2)
由于上述递归公式具有重叠的子问题，因此我们可以使用动态规划来解决。

class GFG { 
    public int countFriendsPairings(int n) 
    { 
        int dp[] = new int[n + 1]; 
        for (int i = 0; i <= n; i++) { 
            if (i <= 2) 
                dp[i] = i; 
            else
                dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]; 
        }   
        return dp[n]; 
    } 
 }

另外一种递归的方式

class GFG { 
    static int[] dp = new int[1000]; 
    static int countFriendsPairings(int n) 
    { 
        if (dp[n] != -1) 
            return dp[n]; 
        if (n > 2) 
            return dp[n] = countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2); 
        else
            return dp[n] = n; 
    } 
  }
  

其实上面的公式类似于斐波那契数，因此可以简化成下面的代码：

class GFG { 
    public int countFriendsPairings(int n) 
    { 
        int a = 1, b = 2, c = 0; 
        if (n <= 2) { 
            return n; 
        } 
        for (int i = 3; i <= n; i++) { 
            c = b + (i - 1) * a; 
            a = b; 
            b = c; 
        } 
        return c; 
    } 
  }
  

最后

以上就是阳光铃铛为你收集整理的朋友配对问题(Friends Pairing Problem)--动态规划的全部内容，希望文章能够帮你解决朋友配对问题(Friends Pairing Problem)--动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。