撇开什么是动态规划不谈，我们先来看看题干:
有500只老虎，1只羊，一片草原。老虎和羊，都可以吃草活着，对，这个题中的老虎可以吃草。老虎呢，也能吃羊，不允许很多只老虎一起吃羊，只允许一只老虎吃一只羊，并且，吃完羊之后，这个老虎就会变成羊。那么问，老虎会不会吃羊？ 提示:老虎很聪明，每只老虎都很聪明。
小A回答
不吃啊，我堂堂威风老虎，干嘛要变成羊？并且变成羊之后，就该被欺负了
老师说
你坐下
小B回答
吃，因为羊肉好吃
老师说
你坐下
小C回答
不吃，羊那么可爱，吃了干嘛，不吃还能多个小伙伴
小M回答
不吃! 要保护生态平衡！
老师说
这题我能不能撤回？
不开玩笑了，答案在下面揭晓，为了不使得一打开页面就看到答案，我加些空格。
10
9
8
7
6
5
4
3
2
1
公布答案：不吃。为什么呢？因为老虎很聪明啊。WTF，这是什么理由？不急不急，看看下面的解释，(先插播一个广告，就是本人非常喜欢的游戏‘逆转裁判’，文字游戏，结局通常是大逆转，太赞。)
无从下手之际，不妨逆转一下思维，直接想500这个数字，怎么也不具有什么代表性，要是能联想起大学时候的数学归纳法，就好办多了。数学归纳法通常用来证明一些看起来就不用证明的东西，无从下手的时候，就找特殊情况，比如无穷小的时候满足，无穷大的时候满足，然后再证明个有代表性的一般特例满足就好了。
那么我们也从特殊情况入手
- 现在只有 1 老虎，1 羊，那么这只羊会被吃吗？
肯定被吃了，老虎吃了羊后，变成羊，也不会有生命危险了。老虎很聪明，干嘛不吃。
- 现在只有 2 老虎，1 羊，那么这只羊会被吃吗？
不会吃。这两只老虎都很聪明，吃了后自己变成了羊，就会被另一只老虎吃掉自己。
- 现在只有 3 老虎，1 羊，那么这只羊会被吃吗？
吃啊，吃! 反正吃完后，变成上面的情况后没有老虎敢吃我了，我得体验体验羊肉。
- 现在只有 4 老虎，1 羊，那么这只羊会被吃吗？
不吃，吃了后变成上面情况后，自己变成了羊，该被吃掉了。
- 现在只有 5 老虎，1 羊，那么这只羊会被吃吗？
吃啊，吃! 反正吃完后，变成上面的情况后没有老虎敢吃我了，我得体验体验羊肉。
- 现在只有 6 老虎，1 羊，那么这只羊会被吃吗？
不吃，吃了后变成上面情况后，自己变成了羊，该被吃掉了。
那么由以上的情况推导一下，是不是规律已经出来了？ 前提不是说了吗，每个老虎都很聪明，500是什么数？是偶数，那么是不会吃的。
动态规划 Dynamic Programming
动态规划意思就是说，大事化小，小事化了。术语的话，包含三个，最优子结构，边界，状态转移公式，举一个最简单的例子，能更好的理解这三个术语
楼梯台阶有12阶，一步只能走1阶或者2阶，那么，请问走完楼梯有多少走法？
- 走到最后一个台阶的前一个情况，只能有两种吧，就是从第11台阶走一步上来，或者从10台阶走两步上来，那么不管有多少走法走到了11阶假设是X种走法吧，假设是Y种走法走到了10阶，那么，走到12阶的走法一定是X+Y，这个是成立的吧。这就是最优子结构
- 那什么是边界呢？本例子中，走到第一个台阶，就一种走法吧，没有台阶，那就0种走法吧，走到第二个台阶，也就2种走法，其实这就是边界了。
- 那么状态转移公式就水到渠成了,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) )
运行结果和之前的相同，如下
（其实这也只是动态规划入门，后续会有进阶题目。其实也没啥人看，只是写给自己记录一下而已）
