sicily 1029. Rabbit

分析：首先通过分析可以得到递推公式为 f(n) = f(n-1) + f(n - m)
那么就是通过上面的递推式来求得 f(d) 的值。一般来说不用递归，因为递归在数值大的时候时间消耗会非常大，那么这里就用记忆法，其实就是用一个数组来保存结果。因为题目里面说明了 d <= 100，所以结果的个数可以用一个 100 的数组来保存。
另外一个就是大整数计算，这里我用一个 string 来表示，虽然看起来有点烦但还是能理解的。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string add(string num1, string num2) {  // 高精度加法
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());

    string::iterator iter1 = num1.begin();
    string::iterator iter2 = num2.begin();

    string str = "";
    int add = 0;
    for (; iter1 != num1.end(), iter2 != num2.end(); ++iter1, ++iter2) {
        int value = (*iter1 - ‘0‘) + (*iter2 - ‘0‘) + add;
        str = (char)((value % 10) + ‘0‘) + str;
        add = value / 10;
    }
    string::iterator iter = (iter1 == num1.end() ? iter2 : iter1);
    string::iterator iter_end = (iter1 == num1.end() ? num2.end() : num1.end());

    for (; iter != iter_end; ++iter) {
        int value = (*iter - ‘0‘) + add;
        str = (char)((value % 10) + ‘0‘) + str;
        add = value / 10;
    }
    if (add != 0)
        str = (char)(add + ‘0‘) + str;
    return str;
}

string getResult(int m, int d) {  // 递推兔子的总数
    string result[103];
    for (int i = 0; i <= d; i ++) {
          if (i <= m) {
              int value = i + 1;
              char t[256];
              sprintf(t, "%d", value);
              result[i] = string(t);
          }    
          else
              result[i] = add(result[i - 1], result[i - m]);  // 递推公式为 f(n) = f(n - 1) + f(n - m)
      }
      return result[d];
}

int main(int argc, char const *argv[])
{
    int m, d;
    while (cin >> m >> d && m != 0 && d != 0) {
        cout << getResult(m, d) << endl;
    }
    return 0;
}