动态规划

在谈动态规划的时候可以从递归来谈起，大部分的题目我们总是可以用递归来解决，先来谈谈递归的问题，递归是自顶向下的处理问题，将大问题拆解成小问题（从大问题出发解决整个问题，默认小问题是已经解决了的，然后通过小问题的解得到大问题的解），递归有两个过程，一个是递，一个是归，可以将递归处理问题的过程看做一课树，首先递处理每一层，如果每一层有两种计算逻辑，则树是二叉树，从最上层递归调用开始，处于树的顶端，然后递至树的下面两个左右子树，然后不断往后递，二叉树的树枝不断增加，直至递至递归函数的返回条件，也就到达了树的叶结点，然后开始归的操作，从树的下面不断计算得到结果，并返回上层，上层的计算结果依赖于其左右子树的计算结果，归至树顶，问题便得到了解决。树的结构很好的体现了递归地分解为子问题的操作，树的每一次分支都是一次递归中递操作的问题拆解过程，然后从树下面开始层层向上，这是递归中归操作，通过子问题的解得到更大的问题的解，从而最终得到最大的问题的解。递归很大的问题是重复结算太多，就像树一样，递归地递操作生成了树，归操作从树最下层开始往上层归，其中每个节点都要计算，但是这些节点有很多是重复的，因此导致大量重复计算。

然后谈谈记忆化搜索问题，其实就是递归的优化问题，记忆化搜索也是自顶向下的处理问题，而且记忆化搜索仍然是递归地处理问题，只不过记忆化搜索的递归相较于普通的递归节省计算量，因为递归当中有很多重复计算，把这些重复计算去除，便可以节省计算量，如何去除这些冗余计算呢？通过一个数组，保存计算过的节点，当计算新的节点的时候，如果其子问题是重复的且已经计算过，则其计算结果应该保存在这个数组中，因此便不再需要重复计算，只需要将数组中保存的计算结果取出来就可以。

最后谈谈动态规划化，动态规划是自底向上的处理问题（首先处理得到最小的问题的解，然后得到递推式，通过小问题的解递推得到大问题的解，最终得到整个问题的解），因此是递推而不是递归。上面谈到对递归的优化得到了记忆化搜索，其中优化过程中的使用数组保存一些计算节点的结果，在后续计算中使用这些结果并减少计算量，本身就是一种动态规划的思想，动态规划就是利用子问题的解得到最终问题的解，并且在计算的时候保存子问题的解，防止重复计算。那动态规划和记忆化搜索的区别在哪里呢?记忆化搜索仍然是一种递归式，而动态规划往往是使用递推而不是递归，递推式更简洁，但是相较于递归更难以理解。当一个问题拆解成两个子问题的时候，普通递归的时间复杂度是O(2**n)  即2的n次方（递归时间复杂度的计算方法：就看递归的一层，一层计算量的层数次方，一层计算量是2，共n层，便是2的n次方），记忆化搜索（不是普通递归）和动态规划的时间复杂度是相同的，都是O(n)。和记忆化搜索一样，也需要额外的开辟一个数组用于保存已经计算过的结点，从而节省计算量，自底向上进行递推，最终得到原问题的解，递归是自顶向下，从原问题出发，不断拆解问题为子问题，将子问题解决以后进行不断归并得到原问题的解（有两个过程，一个是递，一个是归），由于递归是从原问题出发，因此比较好理解，而递推是从原问题的求解方法的最根处出发，递推得到原问题的解，本身找到这个能解决问题的根出就是比较难理解的，因此递推比递归难一些，但是实现以后也很清晰。

leetcode 中有很多动态规划的题目，这里先举出一道比较难的题目，题目难是难在如何分析上面，经过分析之后，这道题目实际上可以转化为之前做过的机器人在方格上行走的问题。

leetcode712题   两个字符串的最小ASCII删除和

题目描述：给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例 1:

输入: s1 = "sea", s2 = "eat" 输出: 231

解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。 在 "eat" 中删除 "t" 并将 116 加入总和。 结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:

输入: s1 = "delete", s2 = "leet"输出: 403

解释: 在 "delete" 中删除 "dee" 字符串变成 "let"， 将 100[d]+101[e]+101[e] 加入总和。在 "leet" 中删除 "e" 将 101[e] 加入总和。 结束时，两个字符串都等于 "let"，结果即为 100+101+101+101 = 403 。 如果改为将两个字符串转换为 "lee" 或 "eet"，我们会得到 433 或 417 的结果，比答案更大。

题目分析：可以将两个字符串看作一个表格的行和列，一个字符串当作行，一个字符串当作列，且字符串的第一个字符位于表格的左上角，这样得到一个表格，题目可以转化成，从左上角出发，每次只能向右或向左或向右下走一格，选择一条合适的路径走到右下角，使得得到路径的整体代价最小。代价的来源是，向右走一格时，行字符是不变的，列字符变化了，当前行字符和列字符相同时代价为零，若两个字符不相同，代价是新的列字符的ASCII值，向下走一格时，列字符是不变的，行字符变化了，当前行字符和列字符相同时代价为零，若两个字符不相同，代价是新的行字符的ASCII值，向右下走一格时，当前行字符和列字符相同时代价为零，若两个字符不相同，代价是新的行字符的ASCII值

leetcode 312 题 吹气球

题目分析 ：https://www.jianshu.com/p/e5d09b074946

在做DP的题目的时候一定要明确四件事情，定义、递推公式、初始化、结果

在这个题目当中，dp[i][j]定义为戳破从i到j这个区间中的气球所获得的收益，不包括区间范围 i 和 j，递推公式为

dp[i][j] = max(dp[i][k-1] + score(k) + dp[k+1][j]) ，对于所有的[i，j] 中的k

初始化，dp[i][j] = 0 对于任意的i 和 j

结果为dp[1][n] 其中n为所有的气球总数

leetcode 5题最长的回文子串

题目分析：首先考虑一下暴力解法，直接遍历所有可能的子串，然后一一判断子串是否回文，遍历所有子串的时间复杂度为O（n2）平方级别，而对于每一个子串都要进行是否回文的判断，这样总的复杂度是立方级别的。考虑优化暴力解法，如何将判断一个子串是否回文改为常数级别复杂度，那么总体时间复杂度就是平方级别的算法了。

当我们判断一个子串为回文子串后，再判断另外一个包含此回文子串的更长子串时，会重复计算内部此子串是否回文，对此进行改进，考虑 “ababa” 这个示例。如果我们已经知道“bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。定义p（i， j）为true 当字符si到字符sj的子串为回文子串，否则为false，如果p（i，j）=true，则当si-1 == sj+1时，p（i-1，j+1）也为true。以上就是动态规划的递推公式。首先定义一个二维dp数组，然后初始化一个字符的回文串和两个字符的回文串，然后可以递推出三个字符的回文串，继而四个字符的回文串......

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if(length <= 1)
            return s;
        
        char[] sChars = s.toCharArray();
        int resultLeft = 0, resultRight = 0;
        boolean[][] dp = new boolean[length][length];
        for(int row = 0, col = 0; row < length; row++, col++){
            dp[row][col] = true;
        }
        for(int row = 0, col = 1; col < length; row++, col++){
            if(sChars[row] == sChars[col]){
                dp[row][col] = true;
                resultLeft = row;
                resultRight = col;
            }
                
        }
        for(int index = 3; index <= length; index++){
            int left = 0, right = index - 1;
            while(right < length && left >= 0){
                if(sChars[left] == sChars[right] && dp[left+1][right-1]){
                    resultLeft = left;
                    resultRight = right;
                    dp[left++][right++] = true;
                }else{
                    left++;
                    right++;
                }
            }
        }
        return s.substring(resultLeft, resultRight + 1);
    }
}