/* 当未走的楼梯大于1时,可以选择走一步或者走两步,每次所做的选择相似, 符合分治法的特性,因此选择分治法,又测试用例有多组,为了避免多组 用例的重复计算,可用一个数组将已经知道的剩下的楼梯可以走的方法种数记录 下来,避免重复计算。 */ #include<stdio.h> int a[45] = { 0 }; int divide(int n) { if (n<2) { return 1; } if (a[n] > 0) { return a[n]; } return a[n] = divide(n - 1) + divide(n - 2); } int main() { int m; int n; scanf("%d", &m); int i; a[0] = 1; a[1] = 1; a[2] = 2; for (i = 0; i < m; i++) { scanf("%d", &n); divide(n - 1); printf("%d ", a[n - 1]); } return 0; }