前端学习算法1 ：老虎和羊，吃不吃问题（动态规划入门）

撇开什么是动态规划不谈，我们先来看看题干:

有500只老虎，1只羊，一片草原。老虎和羊，都可以吃草活着，对，这个题中的老虎可以吃草。老虎呢，也能吃羊，不允许很多只老虎一起吃羊，只允许一只老虎吃一只羊，并且，吃完羊之后，这个老虎就会变成羊。那么问，老虎会不会吃羊？ 提示:老虎很聪明，每只老虎都很聪明。

小A回答

不吃啊，我堂堂威风老虎，干嘛要变成羊？并且变成羊之后，就该被欺负了

老师说

你坐下

小B回答

吃，因为羊肉好吃

老师说

你坐下

小C回答

不吃，羊那么可爱，吃了干嘛，不吃还能多个小伙伴

小M回答

不吃! 要保护生态平衡！

老师说

这题我能不能撤回？

不开玩笑了，答案在下面揭晓，为了不使得一打开页面就看到答案，我加些空格。

10

9

8

7

6

5

4

3

2

1

公布答案：不吃。为什么呢？因为老虎很聪明啊。WTF，这是什么理由？不急不急，看看下面的解释，(先插播一个广告，就是本人非常喜欢的游戏‘逆转裁判’，文字游戏，结局通常是大逆转，太赞。)

无从下手之际，不妨逆转一下思维，直接想500这个数字，怎么也不具有什么代表性，要是能联想起大学时候的数学归纳法，就好办多了。数学归纳法通常用来证明一些看起来就不用证明的东西，无从下手的时候，就找特殊情况，比如无穷小的时候满足，无穷大的时候满足，然后再证明个有代表性的一般特例满足就好了。

那么我们也从特殊情况入手

1. 现在只有 1 老虎，1 羊，那么这只羊会被吃吗？

肯定被吃了，老虎吃了羊后，变成羊，也不会有生命危险了。老虎很聪明，干嘛不吃。

2. 现在只有 2 老虎，1 羊，那么这只羊会被吃吗？

不会吃。这两只老虎都很聪明，吃了后自己变成了羊，就会被另一只老虎吃掉自己。

3. 现在只有 3 老虎，1 羊，那么这只羊会被吃吗？

吃啊，吃! 反正吃完后，变成上面的情况后没有老虎敢吃我了，我得体验体验羊肉。

4. 现在只有 4 老虎，1 羊，那么这只羊会被吃吗？

不吃，吃了后变成上面情况后，自己变成了羊，该被吃掉了。

5. 现在只有 5 老虎，1 羊，那么这只羊会被吃吗？

吃啊，吃! 反正吃完后，变成上面的情况后没有老虎敢吃我了，我得体验体验羊肉。

6. 现在只有 6 老虎，1 羊，那么这只羊会被吃吗？

不吃，吃了后变成上面情况后，自己变成了羊，该被吃掉了。

是不是规律已经出来了？ 前提不是说了吗，每个老虎都很聪明，500是什么数？是偶数，那么是不会吃的。

动态规划 Dynamic Programming

动态规划意思就是说，大事化小，小事化了。术语的话，包含三个， 最优子结构 ， 边界 ， 状态转移公式 ，举一个最简单的例子，能更好的理解这三个术语

楼梯台阶有12阶，一步只能走1阶或者2阶，那么，请问走完楼梯有多少走法？

1. 走到最后一个台阶的前一个情况，只能有两种吧，就是从第11台阶走一步上来，或者从10台阶走两步上来，那么不管有多少走法走到了11阶假设是X种走法吧，假设是Y种走法走到了10阶，那么，走到12阶的走法一定是X+Y，这个是成立的吧。这就是 最优子结构
2. 那什么是 边界 呢？本例子中，走到第一个台阶，就一种走法吧，没有台阶，那就0种走法吧，走到第二个台阶，也就2种走法，其实这就是边界了。
3. 那么 状态转移公式 就水到渠成了,F(n) = F(n-1) + F(n-2)

别说话，看代码

function fun(n) {
  if (n < 0){
	return 0
  }
  if (n === 1){
	return 1
  }
  if (n === 2){
	return 2
  }
  return fun(n-1) + fun(n-2)
}
console.log('12台阶的走法 ：' + fun(12) )
console.log('11台阶的走法 ：' + fun(11) )
console.log('10台阶的走法 ：' + fun(10) )
console.log('9台阶的走法 ：' + fun(9) )
console.log('8台阶的走法 ：' + fun(8) )
console.log('7台阶的走法 ：' + fun(7) )
console.log('6台阶的走法 ：' + fun(6) )
console.log('5台阶的走法 ：' + fun(5) )
console.log('4台阶的走法 ：' + fun(4) )
console.log('3台阶的走法 ：' + fun(3) )
console.log('2台阶的走法 ：' + fun(2) )
console.log('1台阶的走法 ：' + fun(1) )
复制代码

运行结果如下

其实上面代码是存在问题的，有很多重复的计算。不妨把n限定小一些来看 f(4) = f(3) + f(2),而f(3) = f(2) + f(1),f(2)就是重复计算了。那么代码如何进行优化一翻？

看到上面打印的结果，其实也能发现出规律来，就是3的结果，只依赖1和2，那4的结果有只依赖2和3，而1,2的结果又是显而易见的，那么我们可否逆转一下思维，从下而上计算呢？于是代码如下改造，也就是 真正的动态规划实现

function fun(n) {
  if (n < 0){
	return 0
  }
  if (n === 1){
	return 1
  }
  if (n === 2){
	return 2
  }
  var a = 1
  var b = 2
  var temp = 0
  for(var i = 3; i <= n; i++){
	temp = a + b
	a=b
	b=temp
  }
  return temp
}
console.log( '优化版' )
console.log('12台阶的走法 ：' + fun(12) )
console.log('11台阶的走法 ：' + fun(11) )
console.log('10台阶的走法 ：' + fun(10) )
console.log('9台阶的走法 ：' + fun(9) )
console.log('8台阶的走法 ：' + fun(8) )
console.log('7台阶的走法 ：' + fun(7) )
console.log('6台阶的走法 ：' + fun(6) )
console.log('5台阶的走法 ：' + fun(5) )
console.log('4台阶的走法 ：' + fun(4) )
console.log('3台阶的走法 ：' + fun(3) )
console.log('2台阶的走法 ：' + fun(2) )
console.log('1台阶的走法 ：' + fun(1) )
复制代码

运行结果和之前的相同，如下

（其实这也只是动态规划入门，后续会有进阶题目。其实也没啥人看，只是写给自己记录一下而已）