老虎会吃羊吗？🐅🐑

草原上有 1000 只老虎和 1 只羊，老虎吃羊，羊吃草，但是老虎吃完羊会变成羊（一只羊只能被一只老虎吃）

提示:每只老虎都很聪明

归纳

case1: 两只老虎一只羊

不吃：一只老虎吃完羊后变为羊会被剩下的老虎吃

case2: 三只老虎一只羊

吃：一只老虎吃完羊后情景变为 case1

case3: 四只老虎一只羊

不吃：一只老虎吃完羊后情景变为 case2 会被吃

case4: 五只老虎一只羊

吃：一只老虎吃完羊后情景变为 case3

.

.

.

.

.

.

由最基本的归纳法可以判断只有一只羊的时候，偶数只老虎情况下不吃，而奇数只老虎情况下可以吃

引出课题 Dynamic Programming

Dynamic Programming

简单的理解就是从最基本的的情况入手逐渐将整个问题解决，动态规划主要包含以下三种概念

• 最优子结构
• 边界
• 状态转移公式

下面用常见的斐波那契数列（黄金分割数列、兔子数列）来具象化问题

Fibonacci：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…这个数列从第 3 项开始，每一项都等于前两项之和

在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）因此可以直接写出以下代码：

function fn(n) {
  if (n === 1 || n === 2) {
    return 1
  }

  return fn(n - 1) + fn(n - 2)
}

运行结果如下：

console.log(
  `第1项${fn(1)}`,
  `第2项${fn(2)}`,
  `第3项${fn(3)}`,
  `第4项${fn(4)}`,
  `第5项${fn(5)}`,
  `第6项${fn(6)}`,
  `第7项${fn(7)}`
)
// VM455:1 第1项1 第2项1 第3项2 第4项3 第5项5 第6项8 第7项13

现在根据斐波那契数列来解释上面提出的三个动态规划相关的概念

1. 最优子结构：若想求得第 m 项的值，那么只需要去求得第 m-1 和 m-2 的值即可，那么 fn(m-1) + fn(m-2) === f(m) 等式成立
2. 边界: 即范围
3. 状态转移公式：f(m) = fn(m-1) + fn(m-2)

上面的方法其实看起来就是一个最简单的递归，但是性能会有很大的问题，为什么呢？ 具象化来看： 求得 f(5) = ？

• f(5)依赖 f(4)和 f(3)
• f(4)依赖 f(3)和 f(2)
• f(3)依赖 f(2)和 f(1)

显然上面的计算有着大量的重复操作，既然所有的结果都是基于 f(1)和 f(2), 那么从 f(1)和 f(2)的计算开始就避免了重复的计算，也是就动态规划的思想， 代码如下：

function fn(n) {
  if (n === 1 || n === 2) {
    return 1
  }

  let m = 1,
    m_1 = 1,
    result

  for (let i = 3; i <= n; i++) {
    result = m + m_1
    m_1 = m
    m = result
  }

  return result
}

结果和上面是一致的但是性能就会有非常大的提升了

递归

递归： 程序调用自身的编程技巧称为递归（recursion）

那么上面 return fn(n-1) + fn(n-2) 就是一个最普通的递归

这里再引入一个尾递归的概念：就是函数在尾部调用自身

那下面来简单说说为什么上面递归的写法性能会那么差

调用栈随着 n 的增加而线性增加很容易造成内存堆栈溢出。这是因为这种递归操作中，同时保存了大量的栈帧，调用栈非常长，消耗了巨大的内存

将上面方法改用尾递归的写法：

function fn(n, m_1 = 1, m = 1) {
  if (n === 1 || n === 2) return m

  return fn(n - 1, m, m + m_1)
}

此时 fn 每次递归仅仅更新自己的调用栈，性能得到大幅提升 👍

当然所有的递归都可以用循环来实现，不就避免了堆栈溢出的可能了吗 啊哈哈哈哈哈哈

summary

draven：好好看 好好学