[关闭]
@yexiaoqi 2022-05-20T08:42:29.000000Z 字数 702 阅读 351

HJ37. 统计每个月兔子的总数

刷题


题目:有一种兔子,从出生后第3个月起每个月都生一只兔子,小兔子长到第三个月后每个月又生一只兔子。
例子:假设一只兔子第3个月出生,那么它第5个月开始会每个月生一只兔子。
一月的时候有一只兔子,假如兔子都不死,问第n个月的兔子总数为多少?
数据范围:输入满足 1≤n≤31

输入描述:输入一个int型整数表示第n个月
输出描述:输出对应的兔子总数
示例1

输入:3
输出:2

链接:https://www.nowcoder.com/practice/1221ec77125d4370833fd3ad5ba72395


  1. public class Main {
  2. public static void main(String[] args){
  3. Scanner in = new Scanner(System.in);
  4. while(in.hasNext()){
  5. int n = in.nextInt();
  6. //System.out.println(count(n));
  7. System.out.println(dp(n));
  8. }
  9. }
  10. //方法一:递归,每月的兔子总数 1、1、2、3、5、8……斐波那契数列
  11. private static int count(int n){
  12. if(n <= 2)
  13. return 1;
  14. return count(n-1)+count(n-2);
  15. }
  16. //方法二:动态规划,避免递归计算过程中的重复计算
  17. private static int dp(int n){
  18. int[] num = new int[n+1];
  19. num[1] = 1;
  20. num[2] = 1;
  21. for (int i=3; i<=n; i++) {
  22. num[i] = num[i-1]+num[i-2];
  23. }
  24. return num[n];
  25. }
  26. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注