经典C面试题--台阶跳问题与凑硬币问题

    [题目1]：有足够量的2分、5分、1分硬币，请问凑齐1元钱有多少种方法？

此题目咋一看没有什么思路，根据以往经验可能是个递归、分治类似的问题，随着这个思路想：
（1）先不凑一元（100分），先凑1角（10分）怎么解？
（2）先凑5分怎么解？
（3）先凑一分：这个好办，只有一种解法，就是一个一分硬币。
（4）如果已经凑到99分时的方法为f(99)，那么在此基础上凑齐100分的方法只要一种，就是添加一个一分硬币；同理，如果先凑到98分时的方法种类为f(98)，那么在此基础上凑齐一百分的方法有两种，要么使用两个一分硬币，要么使用一个两分硬币。

分析至此，我就想到了之前做过的一个题目：
有一个台阶总共100阶，每次可以跨1阶或2阶，问从地面到台阶顶部总共有多少走法？

要想一步到达第100阶台阶上，只有两种走法，其一是从第99阶上夸一阶到第100；其二是从第98台阶上跨2阶到达100阶。所以有
f(100) = f(99) + f(98)
更一般的：
        f(k) = f(k-1) + f(k-2), 其中k >= 2
有此通项公式，那么编码实现就很简单了，最简单实现的莫过于递归。但这类算法用递归实现效率非常差，因为有大量重复计算，建议采用累加计算的方式。本文就不贴代码了。

类比于上面的台阶跳，如果将本题看着是一个台阶问题，那么步长有1,2,5三种，则
f(100) = f(99) + f(98) + f(95)
更一般的：
        f(k) = f(k-1)  + f(k-2) + f(k-5)

咋一看，上述分析没有问题，按照此通项公式编码也非常容易。但仔细琢磨有感觉不对味（笔者开始也以为到此结束了），进一步分析：
假设f(97)表示已经凑到97分时的总方法数，那么基于此凑到一百分有多少种方法？
[f(97)] + [1,1,1]
[f(97)] + [1,2]
[f(97)] + [2,1]
从这里我们看明白了，上面方法2和方法3在台阶跳中是不同走法，但在凑硬币的时候，是同一种方式。
即，台阶跳是属于排列，而凑硬币则属于组合！按照台阶跳的算法，会存在大量的重复...

重新考虑：假设已经凑足了100分硬币，其中1分硬币有x个，2分硬币有y个，5分硬币有z个，则
x + 2*y + 5*z = 100， 其中x,y,z ∈N
求上述表达是的非负整数解的组数。

int coinDivide(int sum)
{
            int cnt = 0;
            int i,j;
    
            for(i = 0; i <= sum; i++)
            {
                    for(j= 0; j <= (sum - i) / 2; j++)
                    {
                            if ( (sum - i - 2 * j) % 5 == 0)
                            {
                                    printf("%d -- %d -- %d\n", i, j, (sum -i - 2*j) / 5); 
                                    cnt++;
                            }
                    }
            }
            return cnt;
}

另外，上述实现的时候，采用了1分和2分硬币的个数做循环，外循环是101次，内循环是依次[50...0]（步长2）；但如果采用5分，2分做循环的话，外循环次数21次，内循环依次[50...0]（步长5）。可见要少许多次循环。
编码时如果能够注意这类细节，会增色不少。