前几天去面试，做了一份两道算法题的笔试题，第一道没做出来，第二道面试官认为我写的太复杂了，问答的知识还答得不错，问了下薪资，可能认为笔试做的那么烂还要涨薪就让我回去了。这里只写第一道，第二道题比较简单就不写了：题目： 已知每头牛有6年生命，第0年出生，第6年死亡，在第3年和第5年分别产下一头牛。现有一头牛，问N年后牛的数量？*这道题直接用dp有点困难，回来后，迂回了一下先用递归求出前面的几个，然后找规律。
1、递归
int getNums(int age, int current, int n) {
int nums = 0;
if (current == n) {
if (age >= 6) {
return 0;
} else if (age == 3) {
return 2;
} else if (age == 5) {
return 2;
} else {
return 1;
}
} else {
if (age >= 6) {
return 0;
} else if (age == 3 || age == 5) {
return getNums(age + 1, current + 1, n) + getNums(1, current + 1, n);
} else {
return getNums(age + 1, current + 1, n);
}
}
}
打印结果得到：1 1 1 2 2 3 3 3 5 5 6 8 8 11 13 14 19 21 25 32 35 44 53 60 76 88 104 129 148 180 217 252 309 365 432 526 617 741 891 1049 … 可以得到状态转移方程: f(x) = f(x - 3) + f(x - 5);
2、dp
int getNums(int n) {
int[] f = new int[n + 1];
f[0] = 1;
f[1] = 1;
f[2] = 1;
f[3] = 2;
f[4] = 2;
f[5] = 3;
for (int i = 6; i <= n; i++) {
f[i] = f[i - 3] + f[i - 5];
}
return f[n];
}
