首先给出如下的半数集问题
给定一个自然数n，由n 开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n 的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。
首先分析题目意思：已知一个数n，要整数k1∈[1,n/2]，依次放到这个数的左边（实际上就是放到高位），然后再进行类似操作，只不过再次操作时，添加到左边的数k2的取值范围为k2∈[1,k1/2]，然后依次进行操作，直到不能操作为止。当时看到这个问题，第一印象就是用一个变长容器，找到一个元素就添加进去，最后统计元素个数。基于上述流程，很容易用递归的方法写出程序。最初用C++的STL vector容器写出的程序如下：
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 int getScale(int num); 5 int calcHalfSetNum(int startNum); 6 void addElementInHalfSet(int num, int lastNum, vector<int> &set); 7 int main() { 8 int n,i; 9 vector<int> source; 10 while (cin >> n) 11 source.push_back(n); 12 for (i = 0; i < source.size(); i++) 13 cout << calcHalfSetNum(source[i]) << endl; 14 return 0; 15 } 16 int getScale(int num) { 17 int result; 18 result = 1; 19 while (num > 0) { 20 result *= 10; 21 num /= 10; 22 } 23 return result; 24 } 25 int calcHalfSetNum(int startNum) { 26 vector<int> dynArray; 27 addElementInHalfSet(startNum, startNum, dynArray); 28 return dynArray.size(); 29 } 30 void addElementInHalfSet(int num,int lastNum, vector<int> &set) { 31 int i; 32 set.push_back(num); 33 for (i = 1; i <= lastNum / 2; i++) 34 addElementInHalfSet(num + i*getScale(num), i, set); 35 return; 36 }
本身题目不要求输出目标集合中的所有元素，因此没有必要用vector来保存集合中的所有元素。根据题意，很容易得出一个一般性的递推式：h(n)=1+h(1)+...+h(k)，其中k=n/2。得到这个递推式，也很容易使用递归来写出程序。但是，时间复杂度和刚才的程序一样依然是指数阶的，只是常数小一点（省却了容器操作和动态内存分配的开销）。但是基于这个递推式，很容易发现会有很多重复计算，用动态规划的方法能够避免这类重复计算。
在《算法导论》一书中，提及动态规划有两种设计方法。一种方法是带备忘的自顶向下的方法，另一种是自底向上的方法。两种方法具有相同的复杂度，常数略有差别。对于这个问题，显然对于子问题h(i)中i越小，子问题越小，即越基本。一半情况下，会选择自顶向下的方法，在自顶向下的方法中，需要在主体函数外部维护一个额外的数组，来保存中间计算结果。算法导论书中使用的是用一个“引子函数”的方法，即用一个辅助函数，先分配一个数组（更一般的，进行动态数据结构的初始化），然后把这个数组作为参数传递给主体函数，主题函数在递归时，依然将这个数组传递下去，从而保证了在整个递归过程中，所有的子情况都能够访问这个数组。对于这个问题而言，为了简单起见，可以设置一个全局数组。对于辅助数组，还需要做的一点工作就是，需要确认这个数组中的值，是不是我所需要的已经计算的子问题的结果。可以采取的方法很多，这里使用了不属于子问题的解的集合的元素（0）作为标志，有些时候，当问题的解覆盖了整个数据类型的取值范围时，也可能需要更为复杂的方式。
基于这种自顶向下的思路，我的C++代码实现如下：
1 #include<iostream> 2 #include<vector> 3 using namespace std; 4 int calcHalfSetNum(int startNum); 5 int a[10000]; 6 int main() { 7 int n; 8 unsigned i; 9 vector<int> source; 10 while (cin >> n) 11 source.push_back(n); 12 for (i = 0; i < source.size(); i++) 13 cout << calcHalfSetNum(source[i]) << endl; 14 return 0; 15 } 16 int calcHalfSetNum(int startNum) { 17 int result = 1; 18 int i; 19 if (a[startNum] > 0) 20 return a[startNum]; 21 for (i = 1; i <= startNum / 2; i++) 22 result += calcHalfSetNum(i); 23 a[startNum] = result; 24 return result; 25 } 26
对于另一种自底向上的方法，就是从h(1)开始计算，计算h(i)时，所计算过的结果都存放在数组的对应位置里，直接拿来用就可以了，直到i=n时，循环结束。这种方法就不需要在函数体外维护一个数组了，因为不需要递归调用，函数开头声明的数组在整个算法过程中都是可见的。这里是我一个哥们用C写的代码，以供参考：
1 #include<stdio.h> 2 int main() 3 { 4 int a[1000]={0},i,j,n; 5 a[0]=1;a[1]=1; 6 for(i=2;i<1000;i++) 7 for(j=0;j<=i/2;j++) 8 a[i]+=a[j]; 9 while(scanf("%d",&n)!=EOF) 10 printf("%d ",a[n]); 11 return 0; 12 }
最后还要提及一下就是，如果要输出所有元素时，因为每个元素都不一样，动态规划的方法就不可行了。动态规划算法的核心之一要求问题必须有重复的子问题的解。