我们经常会遇到这样的问题：多个元素之间有很多排列组合，让我们选择满足一定条件的最好的。例如：一个字符串可以有n个种子字符串，让我们从中选择最长的回文字符串。（回文串指的是abccba依次等于原串的串）n项有很多组合，让我们选择一个满足weight的最大值小于某个值的组合这些问题最简单的办法我们想到的就是把所有的情况都列举出来，然后做验证比较。比如第一题：我们可以枚举出所有的子串，然后判断是否是回文串，记录最长的那个。第二题：可以枚举出所有的组合方案，然后验证权重是否小于某个值，将满足条件的值最高的方案记录下来。这种把所有的排列组合都枚举出来，然后依次验证比较的思路是最容易想到的，很多问题我们都是这样解决的。不过一些简单场景的业务需求还不错。如果数据规模变大，马上gg。为什么？第一个问题的解法，枚举所有子串，需要枚举所有起点和终点的坐标，然后判断是否为回文。这需要2个循环来枚举子字符串，1个循环来检查它是否是回文并与最大值进行比较。那就是O(n^3)的复杂度。第二个问题的解决方案需要枚举所有的组合。每个项目都有选择和不选择两种情况。需要递归n次才能计算出所有的情况，即总共有2^n种情况。说到的组合法也需要计算m项的值的总和。那就是O(2^n*m)的复杂度。这种解决方案是否可以解决业务问题？是的，其实很多情况下，我们都是用这种简单易想的思路来解决的，但是当数据规模变大的时候，这些方案就不管用了。原因如下图所示：当数据规模比较大时，需要换一种时间复杂度较低的算法。如何降低时间复杂度？现在我们逐个枚举，然后单独判断：每个case都要单独做，所以组合越多，复杂度越高。能否找到各种组合之间的规律呢？比如我们可以从一种情况推导出另一种情况，就不用每次都去验证？比如回文串的问题，如果我们知道i和j是回文串，如果前后两个字符相等，那么i-1到j+1不也是回文串吗？于是可以求出这样一个推导关系：if(str[i]===str[j]&&isHuiwen[i+1][j-1]){isHuiwen[i][j]=true;}having之后有什么变化这个推导关系？我们不需要把每一种情况都一一列举出来，分别验证。从一个初始情况推导出以下所有情况还不够吗？直接从结果推导出来，所以复杂度一下子从O(n^3)降到了O(n)。这种找出各种情况之间的规律，然后根据状态转移方程从初始状态推导出所有状态的算法称为动态规划。背包问题如果能找到结果之间的推导关系，就不需要枚举+验证，直接推导即可。我们来试一试：我们关心的是i件物品，当可用容量为j时，最大值是多少。那么第i项和第i-1项是什么关系呢？是安装还是不安装。如果可用容量j小于第i个物品的重量w[i]，则无法装载。即if(j
