动态规划的简单理解

    明天就要上班了，此刻的我心情激昂澎湃，像是学习、约会之类个人的小事在此时更是显得微不足道哇，哈哈哈..哈哈........呜呜呜呜~

期待上班的眼神

    去洗了个脸，回来接着说噶。

    动态规划（Dynamic Programming，DP）是一种将复杂问题分解成子问题逐步解决的优化技术，它不仅应用于编程领域，也应用于管理学、经济学、生物学。可以用一句话来概括：大事化小，小事化了

    此处引入一篇简单易懂的漫画博文

    若是各位看官无心看画，那且听本汉子给您娓娓道来，事情是这样的：

    有俩耗子唠嗑，一只小灰一只小黄。

    小黄问小灰，10级台阶，每跨一步只能向上一级或者两级台阶，要求用程序求出一共有多少种走法。

    那小灰肯定一脸懵逼呀，说出了几种粗暴的方法（暴力枚举）。

    然后小黄就温柔的调教它呗，思路大概是这样的：

    “灰子，你先琢磨琢磨仅剩一步到达10层台阶会出现几种情况，别想了我告诉吧，两种：一种是乖乖迈一级台阶-从9层台阶到10层台阶；另一种是劈开大跨跨越两级台阶-从8层直接干到10层”。

小灰恍然大悟，小黄继续：

    “灰子，新的问题来了：如果我们已知0级到9级台阶走法有x种，0级到8级台阶有y种走法，那么从0级到10级台阶走法有多少种呀？”

    “黄哥，我挠挠脑袋想一想哦，emmm~有了，我们从9级台阶跳到10级台阶只用一步呴，所以没有什么新的走法，走法数量和0层到9层是一样的呴；从8级台阶跳到10级台阶也只用一步呴，走法数量和0级到8级台阶也是一样的呴；然而走到10级台阶的最后一步也只有两种情况：一种是只需要走一个台阶的情况，另一种是要走两个台阶的情况，现在知道了只走一个台阶的走法有x种，走两个台阶的走法有y种，最后把这两种情况的走法合在一起不就好了呱”。

    “妥了兄得，所以我们得到了一个公式叫F(10) = F(9) + F(8)，简化一下这个公式就是F(n) = F(n-1) + F(n-2)，但是这个公式也是有边界值的，就是n不能小于3，小于3时没有实际意义”。

    问题建模：

    【最优子结构】：F(9) + F(8)

    【边界】：F(1) + F(2)

    【状态转移公式】：F(n-1) + F(n-2)

    想了想其实把上面的公式转换成js函数的形式也很简单吧

    就先简单的嘚吧到这里吧，大致的思路就是将一个大问题（0到10层有几种走法）打散（0到1层，到2层，到3层...），重新组装起来，期间会常用到递归的知识，如有尿点，欢迎吐槽。