方法一：栈括号匹配问题可以用栈的先进后出特性解决，传统括号匹配中栈中存放的是左括号，而现在要求的是最长的括号子串，那么栈中应该存放左括号的下标，用当前右括号下标减去左括号下标可得到匹配的括号子串的长度。当前右括号下标应该减去的是弹出当前栈顶左括号下标后剩下的栈顶左括号下标，因为弹出当前左括号下标表示当前左括号和当前右括号匹配，而中间可能有些括号被匹配消掉了，剩下的栈顶左括号下标表示的就是最开始没被消掉的左括号下标，因此当前右括号下标减去它就得到当前匹配的括号子串长度。当栈中的所有左括号都被匹配消掉时，栈中只剩下一个栈底元素存放最后一个没有被匹配的右括号下标，他表示从这个下标之后就是匹配的括号串...

DP数组应该保存什么？两个字符串的问题可以考虑用二维DP数组，由于题目要求str1转换为str2所需要的最小操作数，因此dp[i][j]应该设置为str1中从开头到第i个字符的子串转换为str2中从开头到第j个字符的子串所需要的最小操作数。最小子问题当str1为空串时，即i等于0时，str2每增加一个字符，str1转换为str2都要插入一个字符，即操作数+1。当str2为空串时，即j等于0时，str1每增加一个字符，str1转换为str2都要删除一个字符，即操作数+1。通过以上两种最小子问题情况可以初始化二维DP数组的边界。如何思考状态转移方程？对于str1的i位置和str2的j位置，如果这两...

暴力枚举法将字符串的分割视为"."的插入，由于要分割出四个数字，所以要插入三个"."。分割的数字最多只有三个，所以第一个"."只能在前三个字符后面插入，后面的两个"."都在前一个"."的后三个字符后面插入。分割的数字范围在[0, 255]范围内，每次分割完要判断分割后的每个数字是否符合范围，如果都符合范围的话就加入候选。当分割的数字字符串只有一个字符时，这个字符必然是符合范围的数字，当分割的数字字符串超过一个字符时，要判断是否有先导"0"的存在，比如说"00","01"这种类型的数字，虽然转换为数字后范围在[0, 255]之间，但是会丢失原字符串的"0"，所以也是不符合规范的。时间复杂度：三层...

中心扩散法 当字符串只有一个字符时，这个字符串必然为回文串。中心扩散法将字符串中的每个字符作为中心，看这个字符串左右两边的字符是否相等，如果相等说明这两个字符和该字符组成的子串也是回文串，则更新这个字符所能组成的回文子串的最大长度，并继续向左右外扩一个字符，直到这两个字符不相等为止。但是中心扩散的方法处理奇数长度的字符串比较方便，可以用一个原字符串中不存在的字符，插在原字符串中的每个字符中间，构造一个新的字符串，假设原字符串的字符个数为n，插入的字符个数必然为n+1，则新字符串的长度为n+n+1=2n+1，这样无论之前的字符串是奇数长度还是偶数长度，都能构造出一个奇数长度的字符串。中心扩...

易错分析DP数组定义的是以当前位置arr[i]结尾时的所有连续子数组的最大和，因为是连续数字的数组，所以增加arr[i]后这个arr[i]必须保证在连续子数组中，所以更新的dp[i]应该要包含arr[i]才能保证arr[i]和前面的数字连续，如果更新中包含了dp[i-1]，当前位置i结尾的所有连续子数组的最大和可能就是dp[i-1]，此时arr[i]就不连续了。 function FindGreatestSumOfSubArray(array) { // write code here const dp = new Array(array.length).fill(-Infin...

如何体现上升的逻辑？定义DP数组存放的是以当前位置i结尾的子序列中的最长上升子序列长度，此时可以在0到i的所有子数组中寻找上升子序列，因为是0到i的子数组，所以保证了j<i，所以当arr[j]<arr[i]时，说明i是上升子序列的一部分，则此时以arr[i]结尾的上升子序列长度为dp[i]=1+dp[j]。如何思考状态转移方程？在0到i的子数组中，遍历每个子数组时都更新dp[i]为当前子数组中以arr[i]结尾的最大子序列长度，dp[i] = max(dp[i], dp[j]+1) /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * ...

背包问题此题可视为背包问题，要兑换的钱数aim为背包容量，arr为各个物品的价值，最少需要arr中的几件物品才能装满背包。如何转换为动态规划思路：DP数组应该存放什么？题目要求的是最少需要多少张arr中的货币才能组成aim的钱数，可以自顶向下分析，组成aim-1的钱数最少需要多少张货币，... ，组成1的钱数需要多少张货币，组成0的钱数需要多少张货币。这样DP数组中存放的就是组成0-aim的目标钱数最少需要的货币数量。最小子问题可以从最简单的情况考虑，如果目标钱数是0，那么组成0的钱数需要0张货币，后面的钱数的最小货币数量都可以通过这个情况由小到大递推得到。其次可以考虑特殊情况，比如但目标钱数...

题意理解数组中的所有数字都必须参与译码，并且数字范围是[1, 26]。两位数组合应该在[10, 26]之间，并且是十位数，如02的组合也是无效的。0作为单数字译码肯定是无效的，0和其他数字组合作为译码时，只有10和20这个组合可以在[10, 26]范围内译码，其他情况都是无效的，此时这个数组就无法译码，译码方式为0。当新加入一个数字时，这个数字可以作为单数字译码，也可以和左边的数字组合后再译码，但这两种译码方式都必须满足[1, 26]范围。最小子问题当数组中只有一个数字时，只有一种译码方式，但要保证这个数字不是0，此时dp[0]=1。其他所有位置的初始译码方式都为0，这是为了考虑数字中含有0的...

动态规划思路题目所求的是左上角到右下角的所有路径数量，那么中间状态为左上角到地图中任意方格的所有路径数量，由于机器人只能往下或者往右移动，因此任意方格的路径数量只跟上一方格和左一方格的路径数量有关，按照这两个方格状态转移到最终方格的路径数量即可。最小子问题当地图大小为1xn或者mx1时，所有方格的路径数量只有1，因此二维dp表的初始状态为当i=0或j=0时为1。状态转移方程由于由于机器人只能往下或者往右移动，因此任意方格的路径数量只跟上一方格和左一方格的路径数量有关，因此dp[i][j] = dp[i-1][j] + dp[i]][j-1] /** * * @param m int整型 ...