活动地址：CSDN21天学习挑战赛
什么是动态规划首先很多人问，何为动态规划？动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。通俗一点动态规划就是从下往上(从前向后)阶梯型求解数值。
(资料图片仅供参考)
那么动态规划和递归有什么区别和联系？
总的来说动态规划从前向后，递归从后向前，两者策略不同，并且一般动态规划效率高于递归。
不过都要考虑初始状态，上下层数据之间的联系。很多时候用动态规划能解决的问题，用递归也能解决不过很多时候效率不高可能会用到记忆化搜索。
不太明白?
就拿求解斐波那契额数列来说，如果直接用递归不优化，那么复杂度太多会进行很多重复的计算。
但是利用记忆化你可以理解为一层缓存，将求过的值存下来下次再遇到就直接使用就可以了。
实现记忆化搜索求斐波那契代码为：
而动态规划的方式你可以从前往后逻辑处理，从第三个开始每个dp都是前两个dp之和。
当然动态规划也能有很多空间优化，有些只用一次的值，你可以用一些变量去替代。有些二维数组很大也可以用一维数组交替替代。当然动态规划专题很大，有很多比如树形dp、状压dp、背包问题等等经常出现在竞赛中，能力有限这里就将一些出现笔试高频的动态规划！
连续子数组最大和给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 :
输入最长公共子序列也成为LCS.出现频率非常高！
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
拿b c d d e和 a c e e d e举例，其的公共子串为c d e。如果使用暴力，复杂度太高会直接超时，就需要使用动态规划。两个字符串匹配，我们设立二维dp[][]数组，dp[i][j]表示text1串第i个结尾，text2串第j个结尾的最长公共子串的长度。
这里核心就是要搞懂状态转移，分析dp[i][j]的转换情况，当到达i,j时候：
如果text1[i]==text2[j],因为两个元素都在最末尾的位置，所以一定可以匹配成功，换句话说，这个位置的邻居dp值不可能大于他（最多相等）。所以这个时候就是dp[i][j]=dp[i-1][j-1] +1;
如果text1[i]!=text2[j]，就有两种可能性，我们知道的邻居有dp[i-1][j],dp[i][j-1]，很多人还会想到dp[i-1][j-1]这个一定比前两个小于等于，因为就是前面两个子范围嘛！所以这时就相当于末尾匹配不成，就要看看邻居能匹配的最大值啦，此时dp[i][j]=max(dp[i][j-1],dp[i-1][j])。
所以整个状态转移方程为：
dp给定两个字符串str1和str2,输出两个字符串的最长公共子串。
例如 abceef 和a2b2cee3f的最长公共子串就是cee。公共子串是两个串中最长连续的相同部分。
如何分析呢? 和上面最长公共子序列的分析方式相似，要进行动态规划匹配，并且逻辑上处理更简单，只要当前i,j不匹配那么dp值就为0，如果可以匹配那么就变成dp[i-1][j-1] + 1
核心的状态转移方程为：
dp分析： 这个问题其实就是上面有几个pat的变形拓展，其基本思想其实是一致的，上面那题问的是有几个pat，固定、且很短。但这里面t串的长度不固定，所以处理上就要使用数组来处理而不能直接if else。
这题的思路肯定也是动态规划dp了，dp[j]的意思就是t串中[0,j-1]长字符在s中能够匹配的数量(当然这个值从前往后是动态变化的)，数组大小为dp[t.length+1]。在遍历s串的每一个元素都要和t串中所有元素进行对比看看是否相等，如果s串枚举到的这个串和t串中的第j个相等。那么dp[j+1]+=dp[j]。你可能会问为啥是dp[j+1],因为第一个元素匹配到需要将数量+1，而这里为了避免这样的判断我们将dp[0]=1,这样t串的每个元素都能正常的操作。
但是有一点需要注意的就是在遍历s串中第i个字母的时候，遍历t串比较不能从左向右而必须从右向左。因为在遍历s串的第i个字符在枚举dp数组时候要求此刻数据是相对静止的叠加(即同一层次不能产生影响)，而从左往右进行遇到相同字符会对后面的值产生影响。区别的话可以参考下图这个例子：
实现的代码为：
至此，简单的动态规划算是分享完了。
大部分简单动态规划还是有套路的，你看到一些数组问题、字符串问题很有可能就暗藏动态规划。动态规划的套路跟递归有点点相似，主要是找到状态转移方程，有时候考虑问题不能一步想的太多(想太多可能就把自己绕进去了)，而动态规划就是要大家对数值上下转换计算需要了解其中关系。
X 关闭
X 关闭
人民币汇率对美元中间价报6.9160 较前一日调降
巴菲特减持比亚迪引热议 任泽平：不要神化巴菲特
银河航天完成新一轮融资 投后估值约110亿元人民币
对标特斯拉 保时捷寻求IPO上市 
中国广电App上架 界面非常简洁
本田中国和东风等将联合成立电池采购公司 确定与宁德时代长期采购
