<!-- index-menu -->
今天在知乎上看见一篇理解动态规划的文章，写得很简单易懂。
首先作者引用了Quora上的一个问题：

How should i explain Dynamic Programming to a 4-year-old?

writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper

"What's that equal to?"

counting "Eight!"

writes down another "1+" on the left

"What about that?"

quickly "Nine!"

"How'd you know it was nine so fast?"

"You just added one more"

"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"

意思很简单，我们通过前面已有的计算结果来计算出下一次的结果会变得很简单，4岁小孩都能计算出来。

动态规划就是利用上一个状态或上两个状态（根据情况来）得到的结果来继续计算下一个状态的值。比较经典的问题参考青蛙跳台阶和斐波拉契数列。首先看青蛙跳台阶：

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
首先我们假设青蛙跳要跳的台阶只有2个，那么青蛙跳上这两个台阶的次数为跳2级一步到位+一步一步的跳跳上台阶两种方案。

那么我们再来看如果台阶变为3的情况：
青蛙跳到阶梯3的情况只能是从

1. 阶梯1跳两步上来
2. 阶梯2跳一步上来
   两种情况，而从阶梯2到阶梯3可能是1步1步跳到阶梯2再到的阶梯3，也有可能是一步到位跳2步到阶梯2到的阶梯的3两种情况，那么跳到阶梯3可以表示为：T[3] = T[2]+T[1]。

以此类推到T[n]阶梯时，跳到T[n]阶梯也只能是从T[n-1]处跳一步到达，或者在T[n-2]处跳2步到达两种情况。因此T[n]=T[n-1]+T[n-2],代码如下：

    public int numWays(int n) {
        if(n==0||n==1){
            return 1;
        }
        int dp[] = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3;i<n+1;i++){
            dp[i] = (dp[i-1]+dp[i-2])% 1000_000_007;
        }
        return dp[n];
    }
}