这周练习动态规划
我们维护一个二维的 dp 数组，其中 dp[i][j] 表示到达当前位置的最小路径和。
接下来找状态转移方程，因为到达当前位置 (i, j) 只有两种情况，要么从上方 (i-1, j) 过来，要么从左边 (i, j-1) 过来，
我们选择 dp 值较小的那个路径，即比较 dp[i-1][j] 和 dp[i][j-1]，将其中的较小值加上当前的数字 grid[i][j]，
就是当前位置的 dp 值了。但是有些特殊情况要提前赋值，比如起点位置，直接赋值为 grid[0][0]，还有就是第一行和第一列，
其中第一行的位置只能从左边过来，第一列的位置从能从上面过来，所以这两行要提前初始化好，然后再从 (1, 1) 的位置开始更新到右下角即可
类似爬楼梯那题
建立一维 dp 数组，其中 dp[i] 表示s中前i个字符组成的子串的解码方法的个数，dp数组长度比输入数组长多1，
并将 dp[0] 初始化为1。现在来找状态转移方程，dp[i] 的值跟之前的状态有着千丝万缕的联系，
就拿题目中的例子2来分析吧(s = "226")，当 i=1 时，对应s中的字符是 s[0]='2'，只有一种拆分方法，就是2，
注意 s[0] 一定不能为0，这样的话无法拆分。当 i=2 时，对应s中的字符是 s[1]='2'，由于 s[1] 不为0，
那么其可以被单独拆分出来，就可以在之前 dp[i-1] 的每种情况下都加上一个单独的2，
这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况，接下来还要看其能否跟前一个数字拼起来，若拼起来的两位数小于等于26，并且大于等于 10（因为两位数的高位不能是0），那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数，
所以最终 dp[i] = dp[i-1] + dp[i-2]，是不是发现跟斐波那契数列的性质吻合了。所以0是个很特殊的存在，若当前位置是0，
则一定无法单独拆分出来，即不能加上 dp[i-1]，就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数，
能的话可以加上 dp[i-2]，否则就只能保持为0了。具体的操作步骤是，在遍历的过程中，对每个数字首先判断其是否为0，
若是则将 dp[i] 赋为0，若不是，赋上 dp[i-1] 的值，然后看数组前一位是否存在，如果存在且满足前一位是1，或者和当前位一起组成的两位数不大于 26，则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可
建立一个二维 dp 数组，其中 dp[i][j] 表示到达 (i, j) 位置所能组成的最大正方形的边长。
我们首先来考虑边界情况，也就是当i或j为0的情况，那么在首行或者首列中，必定有一个方向长度为1，
那么就无法组成长度超过1的正方形，最多能组成长度为1的正方形，条件是当前位置为1。边界条件处理完了，
再来看一般情况的递推公式怎么办，对于任意一点 dp[i][j]，由于该点是正方形的右下角，
所以该点的右边，下边，右下边都不用考虑，关心的就是左边，上边，和左上边。这三个位置的dp值都应该算好的，
还有就是要知道一点，只有当前 (i, j) 位置为1，dp[i][j] 才有可能大于0，否则 dp[i][j] 一定为0。当 (i, j) 位置为1，
此时要看 dp[i-1][j-1], dp[i][j-1]，和 dp[i-1][j] 这三个位置，我们找其中最小的值，并加上1，就是 dp[i][j] 的当前值了，这个并不难想，毕竟不能有0存在，所以只能取交集，最后再用 dp[i][j] 的值来更新结果 res 的值即可
时间复杂度 O(n^2)
空间复杂度 O(n^2)
不像dp的一道题
mx为最大出现次数, 那么就可以分成(mx - 1)块，再加上最后面的字母，每块占n + 1位
时间复杂度 O(n)
空间复杂度 O(n)
将 dp[i][j] 定义成子字符串 [i, j] （这区间形成的字符串）是否是回文串，然后i从 n-1 往0遍历，j从i往 n-1 遍历，
然后看 s[i] 和 s[j] 是否相等，这时候需要留意一下，有了 s[i] 和 s[j] 相等这个条件后，i和j的位置关系很重要，如果i和j相等了，
则 dp[i][j] 肯定是 true；如果i和j是相邻的，那么 dp[i][j] 也是 true；如果i和j中间只有一个字符，那么 dp[i][j] 还是 true；
如果中间有多余一个字符存在（j - i > 2的情况），则需要看 dp[i+1][j-1] 是否为 true，若为 true，那么 dp[i][j] 就是 true。赋值 dp[i][j] 后，如果其为 true，结果 res 自增1
dp[i]数组表示在此位置（i），最长合法子串长度是多少
1.从后往前遍历，因为必须保证是‘（’起始，所以，位置定位在字符串长度的倒数第二个位置（n-2）
2.si = ')' 不用管
3.si = '('，则需要找到右括号和它匹配，可以跳过以i + 1开头的合法子串。i+1开头的合法子串有多长，有dp[i+1]个长度
4.取这些长度之后的一位，即j = i + dp[i+1] + 1;
5.如果j位是')',dp[i] = dp[i+1] + 2
6.如果j位没有到达末尾，还要加上j+1位的dp值
dp[i][j] 表示从 word1 的前i个字符转换到 word2 的前j个字符所需要的步骤
word1[i] == word2[j] 时，dp[i][j] = dp[i - 1][j - 1]，因为字符相同，所以不用转换和dp[i-1][j-1]处相同
不等时
左边dp[i][j-1]对应增加操作
上边dp[i-1][j]对应删除操作
左上dp[i-1][i-j]对应修改操作
最后求他们三种操作中的最小值并+1
Explain：(这里j以i为标准，所以左边是增加j-1+1,上边是j-1)
不像dp的一道题
一维数组sums[m]，记录窗口移动条件下的每行sums值，然后sums累加并和k值比对，找到与k最接近的那个累加值
数据结构采用散列表（hashmap），对于{key:value}键值对，key表示石头的位置，value是step的集合，
step表示青蛙上次跳动到这里时用的步数。
对于每块石头，已知跳到这里用了step步，那么就看从该位置跳step-1、step和step+1能不能跳到新的石头，如果可以，在新的石头的value处加入这个步数
Explain：dp[0] = 0:表示第零位上一步跳动到这里用的步数（没有上一步，所以跳动的步数是0）
dp[i][j] 表示将数组中前j个数字分成i组所能得到的最小的各个子数组中最大值，初始化为整型最大值
来分析一下状态转移方程，如果前j个数字要分成i组，那么i的范围是什么，由于只有j个数字，如果每个数字都是单独的一组，
那么最多有j组；如果将整个数组看为一个整体，那么最少有1组，所以i的范围是[1, j]，所以要遍历这中间所有的情况，
假如中间任意一个位置k，dp[i-1][k] 表示数组中前k个数字分成 i-1 组所能得到的最小的各个子数组中最大值，
而 sums[j]-sums[k] 就是后面的数字之和，取二者之间的较大值，然后和 dp[i][j] 原有值进行对比，更新 dp[i][j] 为二者之中的较小值，这样k在 [1, j] 的范围内扫过一遍，dp[i][j] 就能更新到最小值，最终返回 dp[m][n]
这里面定义了两个数组p和 p_or_l，其中 p[i] 表示数组前i个数字中1以p结尾的排列个数，p_or_l[i] 表示数组前i个数字中以P或者L结尾的排列个数。
这个解法的精髓是先不考虑字符A的情况，而是先把定义的这个数组先求出来，由于p字符可以再任意字符后面加上，
所以 p[i] = p_or_l[i-1]；而 p_or_l[i] 由两部分组成，p[i] + l[i]，其中 p[i] 已经更新了，l[i] 只能当前一个字符是P，
或者前一个字符是L且再前一个字符是P的时候加上，即为 p[i-1] + p[i-2]，所以 p_or_l[i] = p[i] + p[i-1] + p[i-2]。
那么这里就已经把不包含A的情况求出来了，存在了 p_or_l[n] 中，下面就是要求包含一个A的情况，那么就得去除一个字符，
从而给A留出位置。就相当于在数组的任意一个位置上加上A，数组就被分成左右两个部分了，而这两个部分当然就不能再有A，
实际上所有不包含A的情况都已经在数组 p_or_l 中计算过了，而分成的子数组的长度又不会大于原数组的长度，所以直接在 p_or_l 中取值就行了，两个子数组的排列个数相乘，然后再把所有分割的情况累加起来就是最终结果啦
Explain：p_or_l[0] = p[0] = 1;
是因为p_or_l[1] = 2, p[1] = 1；且p[i]= p_or_l[i-1]。倒推得来的
不像dp的一道题,类似双指针算法
Explain:缩减长度时使用的while循环，只要减去再加上1的值不大于0就可以缩减长度
dp[i][j]：i到j之间的最大值
dp转换方程 = 当前最大值(newNums[left] * newNums[i] * newNums[right])
+左边界到i范围内的最大值(dp[left][i])
+i到右边界范围内的最大值(dp[i][right])