阅读 5093

前端学习算法1 :老虎和羊,吃不吃问题(动态规划入门)

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

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

小A回答

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

老师说

你坐下

小B回答

吃,因为羊肉好吃

老师说

你坐下

小C回答

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

小M回答

不吃! 要保护生态平衡!

老师说

这题我能不能撤回?

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

10

9

8

7

6

5

4

3

2

1

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. 现在只有 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) )
复制代码

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

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

关注下面的标签,发现更多相似文章
评论