前言大家好，我是bigsai，好久不见，好怀念（每天都怀念）！很久以前，有朋友被动态规划折磨着。确实，有很多动态规划问题。看的确实太难了，甚至有的题看了解法还要半天才能理解。虽然动态规划的范围确实很广，难度也很大，但是从整个动态规划出现的频率来看，这几种基本的动态规划很容易理解，学习压力也不大，出现频率也比较高。很高。这些常见的动态规划有：连续子数组的最大和、子数组的最大乘积、最长递增子序列（LIS）、最长公共子序列（LCS）、最长公共子串、最长公共子串、不同子序列。什么是动态规划首先很多人问，什么是动态规划？动态规划（DynamicProgramming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。通俗地说，动态规划就是从下往上（从前到后）逐步求解数值。那么动态规划和递归有什么区别和联系呢？一般来说，动态规划是从前到后，递归是从后到前。两种策略不同，一般动态规划的效率要高于递归。但是，必须考虑初始状态和上下数据之间的连接。很多时候可以用动态规划解决的问题也可以用递归来解决，但是很多时候效率不高的话可能会用到内存查找。不明白？以求解斐波那契数列为例。如果不做优化就直接用递归，复杂度太高，会重复很多次计算。但是使用memoization，可以理解为一层缓存，把计算出来的值保存起来，下次遇到的时候直接使用。实现斐波那契记忆搜索的代码是：staticlongF(intn,longrecord[]){if(n==1||n==2){return1;}if(record[n]>0)returnrecord[n];elserecord[n]=F(n-1,record)+F(n-2,record);returnrecord[n];}publicstaticvoidmain(String[]args){intn=6;long[]record=newlong[n+1];System.out.println(F(n,record));}动态规划的方式，可以逻辑上从前到后处理，从第三个开始，每个dp是前两个dp的和.publicintfib(intn){intdp[]=newint[n+1];dp[0]=0;dp[1]=1;for(inti=2;imax)max=dp[i];}returnmax;}ps：有朋友问如何求一个数组的最大和可以不连续？想一想，把包里的正收益一一列举出来。那个问题毫无意义。连续子数组的最大积给你一个整数数组nums，请在数组中找到积最大的连续子数组（子数组至少包含一个数），返回子数组对应的积。示例：输入：[2,3,-2,4]输出：6解释：子数组[2,3]的最大乘积为6。连续子数组的最大乘积也是一个经典的动态规划问题，但它是与普通的动态规划有点不同。如果数据都是非负数，对于连续数组的最大乘积，处理有点类似于前面连续子数组的最大和的处理，要么和前面的乘法一样，要么站在其上自己的。dp[0]=nums[0]dp[i]=max(dp[i-1]*a[i],a[i])但是里面的数据会出现负数，乘以一个负数可能来自themaximum变成了最小的，如果有负数negative，可能又变成了最大的。这个时候怎么想？Easy，我们开两个dp，一个dpmax[]记录乘积的最大值，一个dpmin[]记录乘积的最小值。然后不管当前值是正还是负，每次都更新dpmax和dpmin。这样就可以通过这两个数组来记录产品的绝对值。动态方程也很简单dpmax[i]=max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])dpmin[i]=min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])看一个过程就可以理解，dpmin是起到中间过渡的作用，记录一些可能的负极值在备份的情况下。结果仍然是dpmax中的值。LongestIncreasingSubsequence最长递增子序列，也称为LIS，是出现频率很高的动态规划算法之一。这里为了压力推导300给你一个整型数组nums，在里面找到最长的严格递增子序列的长度。子序列是从数组派生的序列，其中删除（或不删除）元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。输入：nums=[0,1,0,3,2,3]输出：4解释：最长递增子序列为[0,1,2,3]，因此长度为4。对于最长递增子序列，如果不考虑动态规划的方法，使用暴力枚举其实还是挺麻烦的，因为你不知道遇到比前面大的元素要不要自增。比如11031145，这个序列不能选择11011和1345最大，所以暴力枚举所有情况的时间复杂度还是很高的。如果我们采用动态规划的方法，创建的dp[]数组，dp[i]表示以nums[i]结尾的最长递增子序列，dp[i]的解法是枚举第i之前的元素和对应的到最后的最长子序列，找到一个值小于nums[i]且自增序列最长的元素，所以时间复杂度为O(n2)。状态转移方程为：dp[i]=max(dp[j])+1，其中0≤jmax){max=dp[j];}}dp[i]=max+1;//最长的前面加上自己if(maxLen=0;j--){if(t1[j]==s1[i]){dp[j+1]+=dp[j];}}}returndp[t1.length];}}结论到目前为止，简单的动态编程算是完成分享了。大多数简单的动态规划还是有套路的。如果看到一些数组问题和字符串问题，很有可能隐藏了动态规划。动态规划的套路有点类似于递归。主要是求状态转移方程。有的时候不能一步想太多问题（想太多可能会把自己卷进去），而动态规划需要大家把值上下转换。计算需要了解关系。对于复杂的dp问题或者多套壳，确实很难看，但是掌握以上常见的dp问题和背包问题可以解决大部分的动态规划问题（毕竟我们不是搞比赛的，遇到简单的或者中等难度。的）。本文转载自微信公众号「bigsai」
