一道面试题

动态规划，奶牛问题

一只兔子怎么生，我的答案是 0 只

模拟以下不久完事

一只兔子怎么生，人工受精？死的是小兔子还是母兔子？哪有兔子一窝只生一只的，而且兔子的孕期差不多是一个月。兔子是因为什么原因死亡的？如何处理死亡的兔子？
问题太多，打回去重编

把兔子改成细胞不就完了

dp[1-4]=1,dp[i]=dp[i-1]*2, i=5~9, dp[i]=dp[i-1]*2-dp[i-5]不到对不对…死亡是咋死的没太懂

写个程序模拟一下很方便

兔兔那么可爱，你怎么可以让它们死掉

i 从 1 开始，定义 f （ i ）是第 i 天出生的兔子，很容易得到动态规划的方程 f （ i ）= f （ i-4 ）+ f （ i-5 ）+... f （ i-9 ）
初始状态有 f （ 1 ）= 1，f （ 2 ）= f （ 3 ）= f （ 4 ）= 0
举例看看，f （ 9 ）= f （ 5 ）+ .. f （ 1 ）= 2
f （ 10 ）= f （ 6 ）+ ... f （ 1 ）= 2

而一只兔子活 10 天，f （ i ）+ ... f （ i-9 ）就是第 i 天的兔子数量

兔兔为啥死的 如果是类似这次 那不就是 0 只？

@ppyybb 66666，定义为第 i 天出生的就容易多了

dp[i] = dp[i-1] + dp[i-5+1] - dp[i-10+1]

我算, 第 56 已经有 9566300 只兔子了

上面这个 56 天的结果不对, 但是计算机模拟到 60 天就算不下去了

是不是得超级计算机才能算 100 天?

第 2 天有 1 只兔子
第 3 天有 1 只兔子
第 4 天有 1 只兔子
第 5 天有 2 只兔子
第 6 天有 3 只兔子
第 7 天有 4 只兔子
第 8 天有 5 只兔子
第 9 天有 7 只兔子
第 10 天有 10 只兔子
第 11 天有 12 只兔子
第 12 天有 16 只兔子
第 13 天有 22 只兔子
第 14 天有 31 只兔子
第 15 天有 41 只兔子
第 16 天有 54 只兔子
第 17 天有 72 只兔子
第 18 天有 98 只兔子
第 19 天有 132 只兔子
第 20 天有 176 只兔子
第 21 天有 236 只兔子
第 22 天有 318 只兔子
第 23 天有 428 只兔子
第 24 天有 573 只兔子
第 25 天有 768 只兔子
第 26 天有 1032 只兔子
第 27 天有 1388 只兔子
第 28 天有 1863 只兔子
第 29 天有 2499 只兔子
第 30 天有 3355 只兔子
第 31 天有 4507 只兔子
第 32 天有 6052 只兔子
第 33 天有 8123 只兔子
第 34 天有 10905 只兔子
第 35 天有 14644 只兔子
第 36 天有 19664 只兔子
第 37 天有 26399 只兔子
第 38 天有 35441 只兔子
第 39 天有 47586 只兔子
第 40 天有 63895 只兔子
第 41 天有 85787 只兔子
第 42 天有 115176 只兔子
第 43 天有 154639 只兔子
第 44 天有 207629 只兔子
第 45 天有 278772 只兔子
第 46 天有 374284 只兔子
第 47 天有 502524 只兔子
第 48 天有 674712 只兔子
第 49 天有 905898 只兔子
第 50 天有 1216287 只兔子
第 51 天有 1633024 只兔子
第 52 天有 2192560 只兔子
第 53 天有 2943819 只兔子
第 54 天有 3952477 只兔子
第 55 天有 5306729 只兔子
第 56 天有 7125005 只兔子
第 57 天有 9566300 只兔子
第 58 天有 12844065 只兔子
第 59 天有 17244896 只兔子
第 60 天有 23153614 只兔子
第 61 天有 31086890 只兔子

计算机算不下去了
========
代码如下

<?php
function getRabbit($day)
{
//第 1 天有 1 只兔子
$str = '1';

//从第 2 天开始遍历兔子窝
for ($i = 0; $i < $day - 1; $i++) {
//昨天记录的兔子只数
$len = strlen($str);

for ($m = 0; $m < $len; $m++) {
//取出一只兔子
$num = $str[$m];
//让它的年龄增加 1 天
$num++;
//5-10 天的兔子, 要生 1 只兔子
if ($num >= 5 && $num <= 10) {
$str .= 1;
}
//用第 a 天表是第 10 天
$num = $num == 10 ? 'a' : $num;
//记录这只兔子新的年龄
$str[$m] = $num;
}

//第 11 天的兔子已经去世
$str = str_replace('b', '', $str);

$count = strlen($str);
$date = $i + 2;

echo "第{$date}天有{$count}只兔子<br>";
}
}

$a = 61;
getRabbit($a);

这个不对，第 9 天应该有 7 只兔子，实际上按这个公式计算出来是 6 只，后面误差就更大了

Xn 表示第 n 天出生的兔子数量：
Xn = Xn-10 + Xn-9 + Xn-8 + Xn-6 + Xn-5 + Xn-4 （且 X1 = X2 = X3 = X4 =1 ）
第 30 天存活的兔子数量为：
X21+X22+X23+...X30

@dikcen 错了，应该是 X0 = 1，X1 = X2 = X3 = X4 =0

就这个意思，已经把自己绕晕乎了。

兔子生命周期 m，n 天。我想到的算法，时间复杂度 n 空间复杂度 m。不知道能不能更低

你大可不必模拟每只兔兔，记兔兔年龄数量（ 10 ），然后天数递增（ 100 ），复杂也是常量级别，你试试。

@RickyC 你试试换上面方法

直接说瘟疫好了。。。

@pipapa 解决了, 用了您说的统计的思想, 但是没有看懂他们上面的公式, 代码如下
----------------------
<?php
function getRabbit($day)
{
/**
* 初始数组: 用于统计每个年龄的兔子有几只
* 1. 键表示 年龄(几天大)
* 2. 值表示 该年龄的兔子的数量
*/
$arr = [
1 => 1,
2 => 0,
3 => 0,
4 => 0,
5 => 0,
6 => 0,
7 => 0,
8 => 0,
9 => 0,
10 => 0
];

//从第 2 天开始触发循环
for ($i = 0; $i < $day - 1; $i++) {
//先保存昨天记录
$yesterday = $arr;

/**
* 遍历而生成今天兔子年龄的统计情况:
* 1. 今天 1 天大的兔子数量, 是昨天 4-9 天大的兔子的数量的总和, 因为它们今天都到了生育年龄, 各生了 1 只兔子
* 2. 好比: 昨天 2 天大的兔子, 就是今天 3 天大的兔子
*/
foreach ($arr as $k => $v) {

$arr[$k] = $k == 1 ? $yesterday[4] + $yesterday[5] + $yesterday[6] + $yesterday[7] + $yesterday[8] + $yesterday[9] : $yesterday[$k - 1];
}
}

//返回兔子总数
return array_sum($arr);
}

echo getRabbit(100); //第 100 天有 3040556004272 只兔子

实践是检验真理的唯一标准*狗头

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
long[] rabbits = new long[100];
rabbits[0] = 1;
long a=0,b=0,c=0;
Console.WriteLine("第 1 天有 1 只兔子");
for (int i = 1; i <= 99; i++)
{
if (i >= 9)
{
for (int j = 0; j <= 9; j++)
{
rabbits[i - j] -= rabbits[i - 9];
}
}

a = rabbits[i - 1];

if (i < 4)
{
b = 0;
}
else
{
b= rabbits[i - 4];
}

if (i < 9)
{
c = 0;
}
else
{
c = rabbits[i - 9];
}

rabbits[i] = a + b - c;
Console.WriteLine("第{0}天有{1}只兔子,新{2}只", i + 1, rabbits[i],b-c);
}

long d=0;
for (int i = 91; i <= 99; i++)
{
Console.WriteLine("{0}岁的有{1}个", 100 - i, rabbits[i] - rabbits[i-1]);
d += rabbits[i] - rabbits[i - 1];
}
Console.WriteLine(d);
Console.WriteLine(d - rabbits[99]);
Console.ReadKey();
}
}
}
基本思想与 12 楼一致，但在第 n(n>=10)天后，从第 n-9 天到第 n 天要减去第 n-9 天的数量，否则会重复计算。
不过有更简单但不直观的算法，不减去第 n-9 天的数量，算出 92-100 天的增量后相加就是第 100 天的数量

```Javascript
const foo = (n) => {
const rabbitObj = {
0: {
'passDay': 0,
'val': 1
}
};
let id = 1;
let sum = 1; //总数量
//day: 当前天数
const passOneDay= (day) => {
let total = 0; //当天将生产的数量
for (let i in rabbitObj) {
rabbitObj[i]['passDay']++;
if (rabbitObj[i]['passDay'] >= 5 && rabbitObj[i]['passDay'] <= 10) { //5~10 天
total += rabbitObj[i]['val'];
} else if (rabbitObj[i]['passDay'] === 11) { //第 11 天
sum -= rabbitObj[i]['val']; //兔子死去，总数量减去该值
delete rabbitObj[i]; //删除该属性
}
}
if (total) { //当天生产数量不为 0
sum += total;
rabbitObj[id++] = {
'passDay': 1,
'val': total
};
}
}
for (let day = 0; day < n; day++) {
passOneDay(day);
}
return sum;
}
for (let i = 1; i < 101; i++) {
console.log(`第${i}天有${foo(i)}只兔子`);
}
```
结果如下：
第 1 天有 1 只兔子
第 2 天有 1 只兔子
第 3 天有 1 只兔子
第 4 天有 1 只兔子
第 5 天有 2 只兔子
第 6 天有 3 只兔子
第 7 天有 4 只兔子
第 8 天有 5 只兔子
第 9 天有 7 只兔子
第 10 天有 10 只兔子
第 11 天有 12 只兔子
第 12 天有 16 只兔子
第 13 天有 22 只兔子
第 14 天有 31 只兔子
第 15 天有 41 只兔子
第 16 天有 54 只兔子
省略
第 96 天有 935663312748 只兔子
第 97 天有 1256255432122 只兔子
第 98 天有 1686694015993 只兔子
第 99 天有 2264616439357 只兔子
第 100 天有 3040556004272 只兔子

大哥你这第十天的兔子数量不对啊

``````
dp = [1] +[0] * 99

for i in range(100):
if 4 <= i < 10:
for j in range(i-3):
dp[i] += dp[j]
elif i >= 10 :
for j in range(i-9, i-3):
dp[i] += dp[j]
if i <= 9:
print(f'day {i+1} total: {sum(dp[:i+1])}')
else:
print(f'day {i+1} total: {sum(dp[i-9:i+1])}')
``````

对于 11 天以后，只考虑各自 5-10 天里每天新增的兔子数量