算法实验题8.1 半数集问题（记忆化搜索）

题目描述

问题描述：
给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。

实验任务：
对于给定的自然数n，计算半数集set(n)中的元素个数。

思路

刚开始有个数字k，它可以在这个数的左边添加上一系列的数字，但是添加的数字不能大于k的一半，即小于等于k/2。
可以搜索一个数字能够构造的所有集合，添加的数直接枚举即可。那么枚举的这些数字会不会存在重复的情况？比如：126=1，26=12，6。可以发现显然不会，因为最多只枚举到当前数的一半。可以大致证明一下：
如果发现两个数有相同的后缀才有相同的可能会重复。那么两个有相同后缀的数必然是“子树”或者“兄弟”的情况：
如果是“兄弟”显然不会重复，因为前缀中的某个数必然不同；
如果是“子树”由于定义的原因，子树必然由“父亲”结点前面加上某个数传递过来，显然也不会重复，故可以忽略重复的情况，即不用去重。

并且根据上述的递归式可以加上记忆化数组做缓存。

实现

int dfs(int n) {
    if(dp[n]) return dp[n];
    dp[n] = 1; //自己必然是半数集的一份子
    for(int i=1;i<=n/2;i++)
        dp[n] += dfs(i); //生成其他半数
    return dp[n];
}