解题思路:首先列出前几年的数据
| 年份 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |……
| 总数 | 1 | 2 | 3 | 4 | 6 | 9 | 13 | 19 |……
| 成牛 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 6 |……
可以找出规律:
假设第N年的牛的总数为 F(n)
那么前四年中 F(n) = n
后面的年份里 F(n) = F(n-1) + F(n-3)
注意事项:可以用递归解题,但会超时,所以采用动态规划
参考代码:
#include <stdio.h> int main() { int input[20]={0}; int answer[56]={0}; int i=0,j=0; int n; while(1) { scanf("%d",&n); if(n == 0) break; input[i]=n; i++; } //动态规划代码: for(int i=1;i<5;i++) answer[i]=i; for(int i=5;i<56;i++) answer[i]=answer[i-1]+answer[i-3]; while(i--){ printf("%d\n",answer[input[j++]]); } return 0; }
0.0分
1 人评分