[advanced] 6. DP III 区间类 & 匹配类 & 背包类DP - lmcdhr/algorithm-note-from-leetcode GitHub Wiki

DP III

1. 区间类DP

1. 题目类型：

这类DP需要处理的是一段区间上的结果，例如在一段区间上，每次合并/舍弃一些元素，并得出新的结果，最后需要求得的结果一般是一个区间的最大值、最小值或者总值（建议先看例题）

2. 题目思路：

这类题目的思路较为tricky，一般我们dp的思路是从起始状态开始，或者从较简单的情况开始，逐步递推至最后结果/交复杂的状态，这类DP如果使用相同的思路，那么会使得搜索无法产生相同状态，换言之无法使用之前dp所产生的结果从而节约时间，这样就失去了dp相比于暴力dfs优势；

这类区间类问题一般接近处理完整个区间的时候，情况是较为简单的，而头几次处理的时候情况较为复杂，借助之前我们说过的博弈类DP的思考方式，我们先从简单的思路开始思考，从而求出递推方程，所以我们一般从最后状态开始，例如:整个区间处理的最后一步，然后思考整个区间处理的倒数第二步，这样的好处是最后几步的处理过程往往最简单，而且后续的处理也可以用到这些状态的结果，这样也实现了记忆化搜索优化的目的

2. 匹配类DP

1. 题目类型：

大多数是字符串类型，一般题目会包含一个字符串互相匹配，或相等，或包含的条件限制，一般是字符串经过一定处理之后与另外一个字符串互相匹配的问题

2. 解题思路：

这类问题是DP中较为直接的一类问题，字符串操作一般都可以使用dp来解答，因为字符串的处理一般是按序的，完美符合dp的要求，而匹配类问题一般我们需要新开一个二维数组，dp[i][j]一般表示字符串从i到j形成的子字符串的匹配问题，我们只需要从头至尾推导一下，填写一下表格，就可以发现其中的规律，一般dp矩阵中的一个点dp[i][j]经验上大多会与他的左上，左侧，上侧三个结点有关系，我们也能发现这种DP一般只需要保存两行信息，因此可以使用滚动数组优化

3. 矩阵的定义

匹配类dp一般是字符串处理，而字符串可能为空，因此我们定义矩阵的时候，一般会多留出来一行和一列，作为二者可能为null的情况，并对这一行一列进行初始化。这种做法可以推演到所有处理string/数组的题目

3. 背包类DP

1. 题目类型

题如其名，是一种让我们拼多多的题，例如使用数组内的元素加和组成一个更大的数字，就像给予一个指定大小的背包，有给予一些固定大小的物品，让我们尽量填满背包；题目的问题大多是问能不能填满，尽可能填满的最大值，填满背包的不同种方式等等

2. 解题思路

这种类型的问题的解题思路依据DP的基本思路，从最简单状态开始考虑，随后逐步递进，每一步考虑的方法是是否要选用当前的元素：例如我们有一个容积为9的背包，数组中第三个元素为4，那么我们处理dp[3][9]时，有两种可能：选取4或者跳过4，如果选取4，那么我们需要之前的两个元素填满大小为5的容积，以保证能填满9，于是问题就变成了dp[3-1][9-4]=dp[2][5]，如果不用这个4，那么我们需要前面的两个元素独自填满9，问题就变成了dp[3-1][9]=dp[2][9]。

由此我们可以看出这类问题的解题思路：定义一个dp矩阵，横向是背包的不同可能的容积，纵向是物品的大小，这里要注意，我们需要额外留出一行一列，因为无论是背包还是物品，都可能为0，因此矩阵的维度为[物品数组.length+1][背包容积+1]，随后根据题意进行初始化，一般是填满第一行和第一列，随后开始根据之前的思路进行推导，分为取用当前元素和弃用当前元素

这类问题有不同的问法，有的是问能不能填满；有的是问有多少种办法填满；还可能是让你尽可能填满，问最大能装多少。因此根据不同的题意，我们矩阵中应该填入不同的元素，一般是boolean或者int

0-1背包和0-n背包

这类问题分为两类：0-1背包和0-n背包问题，0-1背包就是每种物品非0即1，取或者不取，取也只能取一次；0-n背包是不但可以取，还可以取若干次。因此我们处理问题的时候，这两种有一些不同，区别在于0-1背包我们递归的时候只需要考虑取或者不取即可，但是0-n的话，我们需要写一个while循环，例如当前处理的元素价值是3，背包容积是10，那么我们需要while循环遍历3这个元素被取了0次到3次这4种情况，因为只有这四种情况是有意义的，可能填满背包的情况

4. 栗子

1. 区间类DP

1. 区间类经典题 lintcode 476. Stone Game

https://www.lintcode.com/problem/stone-game/description

题目：

给予一个数组代表很多堆石子，里面每个元素代表每堆石子的石子数量，现在我们通过两两合并的方式合并这些石子到一堆，合并的石子堆必须是相邻的两堆，而且这两堆石子合并的花费是两堆石子中石子数量的总和，求最后将这些石子和为一堆的最小花费
思路：

这道题有的人第一时间想到贪心，认为每次只要合并加和最小的那两个，那么一定最后合并的费用也是最少的，然而并不是，比如这个反例：[6 , 4, 4, 6]，我们根据贪心算法，第一时间合并4和4，变为[6 , 8 , 6]，随后变成[14 , 6]，最后变成20，整个过程花费8+14+20 = 42, 然而我们的最优解是先合并6和4,变成[10,4,6]，随后再合并4和6，最后变成20，整个过程花费10+10+20=40，少于贪心的42，所以说贪心算法极难证明正确性，面试里尽量不要使用

如果按照正常思路来想，开始是[6, 4, 4, 6]，我们随机合并一堆，有三种结果，三种结果的数组长度都是3，再往下一步数组长度就是2，最后是1，这就是一个暴力dfs求解办法，而且我们发现我们先生成了较长的数组结果，但是dp里我们一般先生成较短或者较为简单的结果，这样可以保证后续我们可以用的上这些结果，比如如果我们有[4, 6]合并的结果，那么之后无论是[4, 4, 6]合并还是[6, 4, 4, 6]合并，我们都能用得上；因此我们发现这种想法的问题：想反了

这里我们换一个栗子：[6, 4, 3, 5, 7],根据之前说的新思路，这次我们从最后开始想，最后那步是什么呢？就是最后两堆合成最后一堆的那个状态，而且这一步无论怎么合并，花费都是数组的sum也就是25，虽然结果一样，但是合成的这两堆有不同的可能，可能的情况有nums.length-1种，便是根据数组中间的空隙，分别将整个数组分为两半，例如我们在4和3中间切开，就变成了[6, 4]和[3，5，7]的合并，也就是nums[0~ 1]和nums[2~ 4]的合并，合并的费用是两个子数组的和，sum[0~ 4]，现在我们知道了，这种切分方式的总花费是：两个子数组合并的费用，加上两个子数组形成的费用，对于切分点k=1，也就是sum[0~ 4]+cost(nums[0~ 1])+cost(nums[2~ 4])；随后的问题就是求得这两个子数组的cost，那么这两个子数组，我们也可以使用切分的办法来分别求得他们的结果，接下来的问题就变成了不断地求解左半边和右半边数组的子问题，这个问题会一直递归到切分到的数组长度为2（我的程序里是1，return 0），这样直接返回两个数组的和即可，这样我们就实现了整个步骤的推导：我们定义一个二维dp记忆矩阵，里面dp[i][j]代表一个从下标i到j这堆石子合并为一堆的最小花费，对于这个子数组，我们使用循环对这个子数组进行切分，对于一个数组的不同切分点，一直递归求解，随后return，并将不同切分结果中最小的那个填入dp数组，如果我们将切分位置下标记为k，那么推导方程可以记为：

   for(k from i to j):
       dp[i][j] = math.min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[i,j])

这样我们就实现了从最后状态推导最初状态的过程，最后的结果返回dp[0][nums.length-1]即可，即将整个数组合并的费用，这里还有一个小技巧，就是使用prefix sum求每次合并的费用，因为题目要求了合并的必须是连续的石子堆，因此我们可以使用prefix sum求出这段连续区间的和，在循环求解前，我们使用n²的时间预处理一下就可以了；本题还有一个需要注意的地方就是search函数里切分点for循环的范围，即[start,end)我们可以包含start，意为一个切分出来的数组是第一个元素，但是不能包含end，如果包含，那么k=end的时候，数组相当于没有切分，如果只想要最后一个元素作为一个单独的子数组，那么k应该等于end-1，这里需要注意一下

代码：

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] A) {
        // write your code here
        
        if(A == null || A.length == 0)
            return 0;
        
        int m = A.length;
        int[][] dp = new int[m][m];
        int[][] visited = new int[m][m];
        
        int[][] prefixSum = new int[m][m];
        for(int i=0; i<m; i++){
            prefixSum[i][i] = A[i];
            for(int j=i+1; j<m; j++){
                prefixSum[i][j] = prefixSum[i][j-1] + A[j];
            }
        }
        
        return search(A,dp,visited,prefixSum,0,m-1);
    }
    
    private int search(int[] A, int[][] dp, int[][] visited, int[][] prefixSum, int start, int end){
        
        if(visited[start][end] == 1){
            return dp[start][end];
        }
        if(start >= end){
            return 0;
        }
        if(start+1 == end){
            int temp = A[start]+A[end];
            visited[start][end] = 1;
            dp[start][end] = temp;
            return temp;
        }
        
        dp[start][end] = Integer.MAX_VALUE;
        for(int i=start; i<end; i++){
            dp[start][end] = Math.min(dp[start][end], search(A,dp,visited,prefixSum,start,i)+search(A,dp,visited,prefixSum,i+1,end)+prefixSum[start][end]);
        }
        visited[start][end] = 1;
        return dp[start][end];
    }
}

stone game变种题 leetcode 312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

题目：

有一个数组，代表一排气球，每个元素代表每个气球有固定的分值，现在我们每次可以打爆一个气球，并获得相当于气球分值与他两侧气球的乘积(nums[i]* nums[i-1]* nums[i+1])的分值，如果某一侧或者两侧没有气球，那么该侧气球的分值按照1处理，并且打爆后，该气球左右两边的气球就变为相邻的气球，求打爆所有气球可以获得的最大分数
思路：

本题相较于上一题，多了一个条件，那就是打爆一个之后，两边的气球变成相邻的了，如果正面硬刚，这个限制条件的处理会有点麻烦，我们还是使用前面的思路，先定义dp[i][j]表示打爆从i到j的气球获得的最大分值，而总体的思路也是从最后往前推，即先考虑最后一个被打爆的气球，随后考虑倒数第二个被打爆的气球，直至初始状态（一个都没打爆）；接下来我们推到状态转移函数，对于一个区间dp[i][j]，我们可以按照上题的思路，用for循环遍历区间内所有下一次可能被打爆的气球，并使用递归求得最大的分数，填入dp矩阵，即可，方程可以大致理解为：

for(i from start to end):
   dp[start][end] = Math.max(dp[start][end], search(start,i-1)+search(i+1,end)+bonus)

本题计算bonus（打爆气球的分值）的过程比较难以理解，即我们计算一个区间的结果时，bonus是被打爆的气球乘以哪两个气球的值？是气球两侧的元素吗？还是其他位置呢？本题我们考虑问题是从最后一个被打爆的气球开始，到倒数第二个，一直到倒数第nums.length个，也就是现实中第一个被打爆的气球，比如我们现在有一个区间[3,1,5,8]第，一步我们假设1最后被打爆，那么我们接下来处理的就是[3],[5,8]加上最后打爆1所产生的bonus，我们再从这里面挑选5作为下一个（倒数第二个）被打爆的气球，那么计算5的时候，他的bonus如何计算呢？是5* 8* 3吗？并不是，因为虽然我们第一个挑出去了1，但是实际上1是最后被打爆的，5是倒数第二个被打爆的，所以说5被打爆的时候，1还没有被打爆，但是其他的元素，3和8，其实已经被打爆了，也就是说我们已经挑选出去的元素其实在现实中是后于我们还没被处理的气球被打爆的，也就是说8或者3先被打爆，随后打爆5，最后打爆1，所以如果打爆5，他的左侧是最后被打爆的1，右侧的8已经被打爆，没有元素，所以右侧按照题意按1处理，bonus其实是1* 5* 1，总结起来其实是当前被打爆的气球的价值乘以区间外侧两端的那个元素，也就是nums[i]* nums[start-1]* nums[end+1]；这个结果产生是的原因是我们整个过程是倒序思考的，这也是区间类dp的惯用思路，因此会很绕，大家自己画个图，多加思考

本题还有一个小的处理技巧，就是题目说了两端没有元素的话，按照1处理，如果正常写，需要判断左侧，右侧，或者两侧有没有元素，十分麻烦，我们新定义一个长2位的数组，在原数组左右两侧加一个1，中间copy原数组，然后处理范围改为从1到nums.length即可省略那些判断过程

代码：

class Solution {
    public int maxCoins(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        
        int m = nums.length;
        int[] newNums = new int[m+2];
        newNums[0] = 1;
        newNums[m+1] = 1;
        for(int i=0; i<m; i++){
            newNums[i+1] = nums[i];
        }
        int[][] dp = new int[m][m];
        int[][] visited = new int[m][m];
        for(int i=1; i<m+1; i++){
            dp[i-1][i-1] = newNums[i]*newNums[i-1]*newNums[i+1];
        }
        
        return search(0,m-1,dp,visited,newNums);
    }
    
    private int search(int start, int end, int[][] dp, int[][] visited, int[] nums){
        if(start > end)
            return 0;       
        if(visited[start][end] == 1)
            return dp[start][end];
        if(start == end){
            visited[start][end] = 1;
            return dp[start][end]; 
        }
        
        for(int i=start; i<=end; i++){
            int production = nums[i+1]*nums[start]*nums[end+2];
            dp[start][end] = Math.max(dp[start][end], search(start,i-1,dp,visited,nums)+search(i+1,end,dp,visited,nums)+production);
        }
        
        visited[start][end] = 1;
        return dp[start][end];
    }
}

3. 三维区间dp leetcode 87. Scramble String

https://leetcode.com/problems/scramble-string/

题目（不好理解，请打开网页看原题描述）：

新定义一个scramble的关系：将一个字符串任意按顺序拆分看做一个二叉树状结构，将任意一个非叶结点的node的两个children结点的内容互换，即获得了一个string的sramble string。现在给予两个string，要求求出他们是否互为scramble
思路：

本题的第一个重点在于如何判断两个字符串是不是scramble的，因为题目中一个字符串可以被任意划分入树状结构内，例如great，我可以分为gr和eat，随后gr有两个子节点g和r，我swap他们，单词就变成了rgeat，所以我只要找出所有可切分的点，随后按长度切分两个string，并分别判断对应的两个子切分块是不是scramble就可以了，比如great和rgeat，我将他们分成gr+eat，rg+eat，随后分别比对，这样将问题划分为了一个递归问题。这种想法总的思路没错，但是细节出了问题，就是这种思路默认scramble是按序的，但是也可能存在rotate的可能，即我将root结点的两个子节点swap，great还是分成gr和eat，但是swap后变成了eatgr，这样的话其实是第一个字符串的前两个字符gr和第二个字符串的后两个字符的gr是互相scramble的；所以我们考虑两个字符串的时候要考虑两种情况：
1. swap的不是根节点：那么大的顺序不会变，切分后按照同样的顺序（比如2+4对比2+4）比较即可
2. swap的是根节点：那么整个字符串实际被rotate，对比的顺序变成了2+4和4+2，那么我们需要改变一下对比的顺序，让2和2对比，4和4对比，
于是我们可以大概知道dp定义的方式：定义两个字符串的起点位置，随后定义对比的长度len，所以这应该是一个三维的dp，即dp[i][j][len]：string1从i开始，string2从j开始，比对一个长为len的子字符串是不是互相scramble的，而且有两种情况，rotate和不rotate的对比情况，两种只有有一个返回true即可。而对于是否是rotate，我们还是用之前的办法，遍历所有可能的切分位置，直至找到一个返回true的切分位置，或者所有切分位置都不满足最后返回false，dp推导函数可以概括为：

dp[i][j][len] = {for(k from 1 to len-1)
   (dp[i][j][k]&&dp[i+k][j+k][len-k]） ##顺序比对 || （dp[i][j+len-k][k] && dp[i+k][j][len-k]） ## rotate比对
}

我们求解完所有的dp点位之后，返回dp[0][0][string.length()]即可

代码：

class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length())
            return false;
        if(s1.equals(s2))
            return true;
        
        int m = s1.length();
        boolean[][][] dp = new boolean[m][m][m+1];
        for(int i=0; i<m; i++){
            for(int j=0; j<m; j++){
                dp[i][j][1] = (s1.charAt(i) == s2.charAt(j));
            }
        }
        
        for(int len = 2; len<=m; len++){
            for(int i=0; i<m-len+1; i++){
                for(int j=0; j<m-len+1; j++){
                    for(int k=1; k<len; k++){
                        if((dp[i][j][k] && dp[i+k][j+k][len-k]) ||(dp[i][j+len-k][k] && dp[i+k][j][len-k]))
                            dp[i][j][len] = true;
                    }
                }
            }
        }
        
        return dp[0][0][m];
    }
}

2. 匹配类DP

匹配类经典题 leetcode 1143. Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/

题目：

给予两个字符串，求两个字符串的最长公共子字符串的长度，例如：abcde&acf，return 2（ac）
思路：

如果按照以前的思路，那就是暴力遍历，因为要求按序匹配，使用双指针，从头到尾依次遍历，不过这样就变成了之前说的暴力dfs，这里我们使用dp进行优化，之前我们说过，字符串类问题非常适合使用dp，因为字符串的处理往往是从一开始按序推导到最后，而且规律也很容易找到。

本题中，我们需要求两个字符串之间的一个匹配字符串的长度，因此我们需要定义一个二维矩阵，dp[i][j]代表第一个字符串从头到i，第二个字符串从头到j，可以生成的匹配字符串的长度，这里我们多保留一行和一列，意为当两者其中之一为空或者两者都为空时，匹配字符串的长度，毫无疑问里面应该置0，多的这一行一列可以方便我们的推导。随后我们开始初始化，将第一行第一列置为0。随后我们开始状态函数的推导，这里举个例子，假如在上述例子中，我们遍历到了ab和a，此时公共字符串长度为1，可以很容易的看出，如果两者下一个字符相同，比如是abc和ac，那么公共字符串的长度在ab和a的基础上加了1；不过如果下一个字符不同，比如字符串变成了abcde和ast，那么此时能形成的公共字符串长度不变，要么与ab和as所组成的公共字符串的长度相同，要么与abc和a所组成的公共字符串的长度相同（因为新加入的字符不能增加长度），由此我们可以总结出递推公式：

for(i from 0 to s1.length)
   for(j from 0 to s2.length)
      if(s1[i] == s2[j])
         dp[i][j] = dp[i-1][j-1]+1
      if(s1[i] != s2[j])
         dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

我们随后使用滚动数组优化，将空间复杂度降至n，最后返回dp[m][n]即可。匹配类问题其实并不难，我们没有思路的时候，直接手动填写表格，都能发现其中的规律，比如这道题，我们如果手动填写dp表格，便会发现只有两个字符串遍历到的字符相同的时候，长度才会+1，否则就是左侧元素和上边元素的最大值，有的时候我们并不知道为什么，甚至转换方程不是最正确的写法，不过结果也是一样的，所以这类问题一定要敢写敢推，一般写出答案都不是问题，有的时候需要根据答案来逆推原因（用答案解释原因）

代码：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0)
            return 0;
        int m = text1.length();
        int n = text2.length();
        
        int[][] dp = new int[2][n+1];
        for(int j=0; j<n; j++){
            dp[0][j] = 0;
        }
        
        for(int i=1; i<m+1; i++){
            for(int j=0; j<n+1; j++){
                if(j == 0)
                    dp[i%2][j] = 0;
                else if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i%2][j] = dp[(i-1)%2][j-1]+1;
                }else{
                    dp[i%2][j] = Math.max(dp[i%2][j-1], dp[(i-1)%2][j]);
                }
            }
        }
        
        return dp[m%2][n];
    }
}

抽象匹配类 leetcode 72. Edit Distance

https://leetcode.com/problems/edit-distance/

题目：

给予两个字符串，现在要从第一个字符串经过若干操作变为第二个字符串，操作包括增加一个元素，删除一个元素，替换一个元素，要求求得最少多少步操作可以完成转换
思路：

不难发现是匹配类问题，但是这种增删改的问题，第一时间想到的是类似于之前word ladder一样使用dfs/bfs，这样时间复杂度是指数次的，这里我们尝试使用dp进行优化

上一道题我们使用dp[i][j]定义了两个字符串在一定范围内最大公共字符串的长度，本题我们需要求距离，那么我们的定义就要改为两个字符串在一定范围内转化的步骤（距离），上一题中我们将两个字符串最大公共字符串的问题化解为了两种情况（相等与不等），并且每种情况都可以由之前已经存在的结果得出，那么本题中，我们也可以按照这两种思路思考，如果遍历到的字符相同，那么距离不变，直接继承，不过这三种操作在dp中的推导关系并不像上一题那么直接，因此我们需要先分析这三种操作，比如我们现在正在求解dp[i][j]，那么增，删，改这三种操作分别可以在dp矩阵中的什么位置求出呢？这里我们先从第一行第一列来思考，前面说过匹配类dp一般都会流出一行表示某个或者两个字符串为空的情况，那么这道题里这一行/列如何初始化呢？先看第一列，第一列的情况是s2为空的情况，那么随着s1长度的增加，我们需要s2一直add相应的字符才能保证二者的匹配，也就是说数组中往下的方向其实代表着add，而这一列里面的值就是对应的s1遍历到的长度，意为s2一直加字符，知道与s1长度相等；同理第一行，因为此时s1为空，所以随着s2一步步加长，我们需要一直删除s2的元素，因此里面的元素也与s2遍历到的长度相同，我们也可以认定横向代表着delete；我们可以看出，这里我们是以s1为基准，这样方便思考，大家也可以使用s2位基准，一样没有问题；那么对角线方向毫无疑问就是替换元素的操作了

因此对于dp[i][j],他可以根据当前元素是否相等分为两种情况，相等：直接继承左上元素的情况（两个字符串各加一个相同的字符，距离不变），如果不相等，那么需要操作，我们可以从左侧add，上侧delete，或者左上replace，我们选取三者中最小的，再+1代表我们进行了一步操作，将结果填入dp表格即可。我们照旧可以使用滚动数组优化空间复杂度

本道题代码并不难，但是难点在于将以某一个string为基准，研究清楚三种操作在dp矩阵里的位置关系，如果我们思考的时候没有一个基准string，那么就很难思考清楚了
代码：

class Solution {
    public int minDistance(String word1, String word2) {
        if(word1 == null || word1.length() == 0)
            return word2.length();
        if(word2 == null || word2.length() == 0)
            return word1.length();
        
        int m = word1.length();
        int n = word2.length();
        int[][] distance = new int[2][n+1];
        
        for(int i=0; i<n+1; i++){
            distance[0][i] = i;
        }
        
        for(int i=1; i<m+1; i++){
            for(int j=0; j<n+1; j++){
                if(j == 0)
                    distance[i%2][j] = i;
                else if(word1.charAt(i-1) == word2.charAt(j-1))
                    distance[i%2][j] = distance[(i-1)%2][j-1];
                else
                    distance[i%2][j] = getMin(distance[(i-1)%2][j], distance[(i-1)%2][j-1], distance[i%2][j-1])+1;   
            }
        }
        
        return distance[m%2][n];
    }
    
    private int getMin(int x, int y, int z){
        if(x<y){
            if(z<x)
                return z;
            else
                return x;
        }else{
            if(z<y)
                return z;
            else
                return y;
        }
    }
}

用答案解释原因 leetcode 115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

题目：

先给予两个string，一个为主(s1)，一个为辅(s2);现在要求求出s1中包含多少个s2，例如：bagbgbag, bag, return 4,这种包含可以用s1删除若干个字符形成，但是最后的结果必须顺序也跟s2一样
思路：

典型的字符串匹配问题，这道题其实大多数人第一次做出来都是直接填写dp矩阵发现了规律，但是并不知道为什么：我们定义dp[i][j]是s1从头至j，s2从头至i，最多的匹配次数，通过填写矩阵，我们发现规律是如果i和j位置对应的字符相等，那么dp[i][j] = dp[i][j-1] + dp[i-1][j-1]，如果不等，那么等于dp[i][j-1]

为什么呢？不相等的时候很好理解，新加一个不相干的字符，那么跟之前的状态一样，但是为什么相等的话是左边和左上的两个元素加和呢？（注意，这里我是将主字符串放在横向位置，辅字符串放在竖向位置，如果颠倒，位置可能会有不同）这里举一个栗子，我们假设对比bagbgbag（主）和bag（辅），现在我们已经得知bagbgba和ba,结果是3(dp[i-1][j-1])，bagbgba和bag(dp[i][j-1])，结果是2，我们现在去求bagbabag和bag ,根据之前的推断，结果应该是两者相加，为5，但是为什么呢？
1. 我们可以发现在这一步两边都加了一个g，而之前没有g的时候，也就是bagbgba和ba的时候，可以匹配到3个ba，现在加了一个g，那么这三个ba可以瞬间匹配为bag，因此有三个可以的
2. 除此之外，如果之前的bagbgba里面本来就有bag，那么我们的辅字符串s2变为bag之后，就不用从原来匹配的ba再加g组成bag，而是直接拿出bag就可以了，因此我们可以从bagbgba里面直接找bag，找到里面本来就有的bag，是2
由此我们可以看出，之所以是这两者加和，是因为获得新的辅字符串，或者说获得了新的要查找的字符串之后，有两种组成方式，一个是从之前少一个字符的辅字符串里加上这个新的字符，第二个是直接从旧的主字符串里面查找这个新的辅字符串，二者相加，既是所有结果。其实这个都是程序写完之后从结果逆推找到的解释，一开始并不能解释清楚为什么，也只是照本宣科填完所有dp矩阵找规律而已，所以说匹配类dp也是一类写起来容易解释起来难的dp
代码：

class Solution {
    public int numDistinct(String s, String t) {
        if(s == null || s.length() == 0 || t == null || t.length() == 0)
            return 0;
        
        int n = s.length();
        int m = t.length();
        int[][] dp = new int[2][n+1];
        
        for(int i=0; i<n+1; i++){
            dp[0][i] = 1;
        }
        dp[0][0] = 1;
        
        for(int i=1; i<m+1; i++){
            for(int j=0; j<n+1; j++){
                if(j == 0){
                    dp[i%2][j] = 0;
                }else if(t.charAt(i-1) == s.charAt(j-1)){
                    dp[i%2][j] = dp[i%2][j-1] + dp[(i-1)%2][j-1];
                }else{
                    dp[i%2][j] = dp[i%2][j-1];
                }
            }
        }
        
        return dp[m%2][n];
    }
}

3. 背包类DP

直白的0-1背包 lintcode 92. Backpack

https://www.lintcode.com/problem/backpack/description

题目：

给予一个数组，代表每个物品的体积，给予一个size，代表背包的容积，现在问能否使用数组内的物品组合以填满背包
思路：

非常直白的背包问题，每个物品最多只可以取1次，因此是0-1背包，我们使用背包dp的标准解答方法：
1. 因为题目问能不能，因此定义一个boolean矩阵，维度是物品数组.length+1 * 背包容积+1，dp[i][j]的含义是使用前i个物品，是否可能填满容积为j的背包
2. 初始化第一行第一列(选用0个物品或者背包容积为0)，背包容积为0的话，不选物品就可以达到要求填满背包，因此第一列初始化为true，但是如果背包容积非0，但是却没有物品，那么无论如何不能填满，因此第一行除了第一个元素以外的其他元素为false
3. 随后开始推导，根据我们之前的思路，取用或者不取用，可以得出方程：

dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j]

我们最后的结果是容积为size的时候，使用所有的物品能否填满，于是返回dp[nums.length][size]即可
代码：

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int sum = 0;
        for(int a: A){
            sum += a;
        }
        if(m > sum){
            return sum;
        }
        
        int n = A.length;
        boolean[][] dp = new boolean[n+1][m+1];
        for(int i=0; i<n+1; i++){
            dp[i][0] = true;
        }
        
        for(int i=1; i<n+1; i++){
            for(int j=1; j<m+1; j++){
                if(j >= A[i-1]){
                    dp[i][j] = dp[i-1][j-A[i-1]] || dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        for(int j=m; j>=0; j--){
            for(int i=0; i<n+1; i++){
                if(dp[i][j]){
                    return j;
                }
            }
        }
        
        return 0;
    }
}

0-1背包马甲题 leetcode 416. Partition Equal Subset Sum && leetcode 322. Coin Change

https://leetcode.com/problems/partition-equal-subset-sum/

https://leetcode.com/problems/coin-change/

题目：

416：给予一个数组，现要求求出是否可能将数组分成两部分（可以不连续，任意pick元素即可），使得两部分的加和相等 322：给予一个数组，代表硬币的值，现在给予一个价值，要求求出最少多少枚硬币可以正好组成（每个硬币最多取一次）这个价值
思路：

这两道题很难看出是背包的马甲题，不过我们仔细思考，0-1背包是用不同的元素来填满指定的size，那么416其实看能不能用一些元素填满sum/2，322是将上一题背包的能否boolean变量变成int型的路径长度，思路是不变的；两个问题一个是改变了问法，一个是改变了要求的东西，其实都是0-1背包

416我们只需要先预处理数组的sum(羡慕python)，先查看是否是偶数，如果是奇数，那么无论如何不能平分，直接false，如果是偶数，就继续按照上一题的思路处理，最后遍历一下dp矩阵最后一列（保证能组成sum/2），如果有一个为true即可

322主要在于改变dp矩阵的意义，之前是能不能，现在是路径长度（硬币数量），那么需要在取或者不取当前元素中选择较小的一个就可以了，我们可以先将矩阵初始化为一个很大的值，第一列根据题意初始化为0（如果需要的价值为0，那么需要0个硬币可以满足条件），之后根据新的思路往下递归，直至最后，如果发现最后一个元素dp[coins.length][amount]是那个很大的值，说明没有更新，也就是说明无法组成这个值，因此返回-1，如果是小于初始值，那么说明有路径可以到达，直接将结果return即可。下面的代码中我将二维数组优化为一维，因此每一列只需要保存一个最小值就行了，其他值在今后的递归中用不到
代码：

class Solution {
    
    public int coinChange(int[] coins, int amount) {
        
        if(amount == 0)
            return 0;
        if(coins == null || coins.length == 0)
            return -1;
        
        int m = coins.length;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount+1);
        
        dp[0] = 0;
        for(int i=1; i<amount+1; i++){
            for(int j=0; j<m; j++){
                if(coins[j] <= i){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);  
                }
            }
        }
        return dp[amount] > amount? -1:dp[amount];
    }   
}

附带价值的0-1背包 lintcode 125. Backpack II

https://www.lintcode.com/problem/backpack-ii/description

题目：

还是用物品塞满背包，但是现在每个物品不但有体积，还有价值，现在要求我们尽量塞满背包，并且要获得最大价值，求这个最大价值
思路：

新加了一个价值，很多小伙伴会机智的使用贪心，即求出物品单位体积的价值，那么一直用单位体积价值最大的物品填满背包就可以了，这当然是错的，反例自己找吧，很好找的；我们还是使用DP，我们需要更改dp矩阵的意义，变为前i个物品尽量填满j的容积，可获得的最大价值，听起来像三维，其实二维就可以了

这里我们需要分开讨论一下，如果当前物品的体积比要填的体积还大，那么这个物品必不可能被使用，那么直接继承上一步中的结果即可，如果比要填的体积小，那么他可以被选用，我们根据使用当前物品或者不使用来求出更大的价值，填入矩阵中

本题有一个看似吓人的点是让我们尽量填满，可以不填满，不过其实这与恰好填满并没有本质区别，我们直接继承上一行的结果，其实就是一种尽量填满的体现，并不需要额外的处理
代码：

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int n = A.length;
        int[][] dp = new int[n+1][m+1];
        
        for(int i=1; i<n+1; i++){
            for(int j=1; j<m+1; j++){
                if(j >= A[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-A[i-1]] + V[i-1]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return dp[n][m];
    }
}

直白的0-n背包 lintcode

https://www.lintcode.com/problem/backpack-iv/description

题目：

还是塞满背包，不过现在一个物品可以选用若干次，求一共有多少种填满背包的可能
思路：

根据我们之前的讲解，0-n背包与0-1的不同在于需要一个额外的while循环来遍历当前物品可能的被取用数量，那么本题的大致思路为：dp中元素的定义为前i个元素填满j的可能组合数量，初始化过后，按照之前的遍历思路来走，每到一个新的j，我们使用while循环，看当前的j能装下多少个nums[i-1]，每次循环我们根据将之前的结果加入到当前的位置上来，就能得出新的位置有多少种可能组合了，新的状态转换方程为：

while(j-k*nums[i-1] > 0 for k++ from 0)
   dp[i][j] += dp[i-1][j-nums[i-1]*k]

我们可以看到，本题不用分取或者不取的情况了，因为我们k=0的时候其实就是不取，两者合为一体了，最后我们返回dp[物品.length][size]即可

代码：

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackIV(int[] nums, int target) {
        // write your code here
        int m = nums.length;
        int[][] dp = new int[m+1][target+1];
        for(int i=0; i<m+1; i++){
            dp[i][0] = 1;
        }
        
        for(int i=1; i<m+1; i++){
            for(int j=1; j<target+1; j++){
                int k=0;
                while(j-nums[i-1]*k >= 0){
                    dp[i][j] += dp[i-1][j-nums[i-1]*k];
                    k++;
                }
            }
        }
        
        return dp[m][target];
    }
}