动态规划：更高效的穷举！

介绍

动态规划并不是一种具体的算法，而是一种思想，个人觉得就是缓存+枚举，把求解的问题分成许多阶段或者多个子问题，然后按顺序求解各子问题。前一子问题的解为后一子问题提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

所以动态规划一般用来求最优解（对子问题进行决策），求种类数（对子问题进行加和）

先分享几个经典的动态规划实现，后续再分析几个面试题

最长上升子序列

来源：LeetCode 300.最长上升子序列
描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,