拆解数字

将任一个数字进行拆解，例如：

3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1　共七种


随便给一个数字，对其进行拆解，并打印可拆解情况和拆解结果数。

这个可以用一个递归来实现，对于任意的整数n,记拆解方式为g, 且作以下假设：
1).最后一个拆数是1，则拆解方式为 g(n-1) + 1，这个+1表示在g(n-1)的末尾加上一个1
2).最后一个拆数是2，则拆解方式为 g(n-2) + 2.依次类推，直到最后一个拆解数为
n-1。
这样就完成了拆解，不过复杂度比较高，可以试着改善一下。

当然，这个没有考虑顺序问题。

没看明白。

不考虑顺序问题，也可以改用组合方式，如下：
对于n = 1 + 1 + 1 + 1 + ... + 1这列组合加数，其中的 + 取任意个（大于等于1个），即从n-1个加号中任意取出m个 1<=m<=n-1,这就对应着一个拆数
所以拆数就是2^(n-1) - 1种。

再考虑一下这种想法：
最少拆解出只有一个加数的，最多拆出有n个加数。
假设已成功拆出有加数为m个的，现在考虑拆出m+1个的情况，即是可以看成是把已经成功拆出的m个中的某一个拆成两个，且如果这m个中有存在至少两个相等，只需要拆出其中一个为两个就行了。直到到最后的n个加数，对于把一个数拆成两个数的方式，这个很简单。这个方案也应该是可行的。

这个可以用动态规划来做：
状态：dp[x][y]表示将x拆分成的最大值为y的方法总数。
过程：dp[x][y] = dp[x-y][1] + dp[x-y][2] + … +dp[x-y][y];
结果：result = dp[n][1] + dp[n][2] + dp[n][3] + … + dp[n][n];

ps：过程中要小心数组越界（要是有代码需求我帮你写哈 ）

如果从拆出的数量来控制状态还是比较麻烦的，不如用拆出来的值中的最大值来控制。

g(n-2) + 2是什么意思？g(n)表示的是最后的结果吗？

就是走楼梯算法:
给定n阶楼梯，可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法，并记录每种走法
递归公式:  f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k)   n>=1
private void climb(int n, int step,List<int> steps)
        {
            if (step > n)
                return;

            steps.Add(step);

            if (n == step)
            {
                //当剩余楼梯的阶数等于第一步所跨的阶数
                //则到达最后一阶楼梯，此时为其中一种走法

                //记录每次走法
                this.count++;
              print(steps);

            }
            else
            {
                //如果没有达到最后一层，则递归剩余楼梯的走法
                //此时，第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定

                for (int i = 1; i <= stemp&& i <= n - step; i++)
                {
                    //递归剩余楼梯第一步的每种走法
                    climb(n - step, i);

                    //退出递归时，清除剩余楼梯的走法
                    //以记录新的走法
                     list.RemoveAt(list.Count - 1);
                }

            }

        }

测试结果 :n=5,step=5时,共有16种走法：
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5

这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了