朋友对算法递归解决方案C [关闭]

Question

鉴于n个朋友，每个人可以保持单身或者可以与其他朋友配对。每个朋友只能配对一次。找出朋友可以保持单身或可以配对的总方式。示例：输入：n = 3输出：4

说明：[{1}，{2}，{3}：所有单个[{1}，{2,3}]：2和3配对，但1是单个]类似[{1,2}，{3} ] [{1,3}，{2}]

最后回答4

在这里，我坚持构造递归

int friends(int i)
{
    if(i==0){
        return 0;
    }
    if(i==1){
        return 1;
    }
    friends(i)=friends(i-1)+(i-1)*friends(i-2);
}

进一步参考：http://www.geeksforgeeks.org/friends-pairing-problem/

Answer 1

你缺少退货声明

return friends(i-1)+(i-1)*friends(i-2);

并且作为链接的代码说，有

if (i <= 2)
           dp[i] = i;

而你在代码中缺少i == 2

例如这个递归工作，我不知道你需要知道更多：

#include <stdio.h>

int friends(int i)
{
    if(i<=2)
        return i;
    return friends(i-1)+(i-1)*friends(i-2);
}
int main()
{
    printf("%d", friends(3));
    return 0;
}