??一)交錯(cuò)字符串:

97. 交錯(cuò)字符串 - 力扣（LeetCode）

一)確定一個(gè)狀態(tài)標(biāo)識(shí):

如果我選擇s1的一段區(qū)間，再進(jìn)行選擇s2得一段區(qū)間，那么s3這個(gè)字符串的長(zhǎng)度就已經(jīng)固定

預(yù)處理:在s1字符串s2字符串和s3字符串前面加上一個(gè)虛擬字符，讓下標(biāo)從1開(kāi)始進(jìn)行計(jì)數(shù)

如果要是從1號(hào)位置開(kāi)始進(jìn)行計(jì)數(shù)的話會(huì)變得十分方便

s1=" "+s1

s2=" "+s2

s3=" "+s3

狀態(tài)表示:dp[i][j]就表示s1中的[1，i]區(qū)間內(nèi)的字符串以及s2[1，j]區(qū)間內(nèi)的字符串能否拼接成s3的[1，i+j]區(qū)間內(nèi)的字符串，如果能夠拼接而成，那么里面存的值就是true，否則里面的值就是false；

二)根據(jù)狀態(tài)表示推導(dǎo)狀態(tài)轉(zhuǎn)移方程:根據(jù)最后一個(gè)位置的情況來(lái)分情況進(jìn)行討論

1)如果s1的[0，i]區(qū)間和s2的[0，j]區(qū)間能夠拼接成s3字符串的[0，i+j]區(qū)間，那么s3字符串的的i+j位置要么是等于s1的i字符，要么是等于s2的j字符，要么都不等于

2)如果能夠拼接而成，要么等于s1的最后一個(gè)字符，要么等于s2的最后一個(gè)字符

if(s1[i]==s3[i+j])那么此時(shí)應(yīng)該研究的就是s1字符串的[0，i-1]區(qū)間內(nèi)的字符串和s2字符串的[0，j]區(qū)間內(nèi)的字符串是否能夠構(gòu)成s3字符串從[0，i-1+j]的子串

if(s1[i]==s3[i+j]) dp[i][j]=dp[i-1][j]

if(s2[j]==s3[i+j]) dp[i][j]=dp[i][j-1]

三)初始化:

引入空串，在原始的dp表中新增加了一行并且新增加了一列

1)dp[0][0]表示的是第一個(gè)字符串是空串況且第二個(gè)字符串也是空串，空串拼接空串當(dāng)然可以

2)現(xiàn)在來(lái)看dp[0][i]位置的值(i>0)，如果第一個(gè)字符串為空，第二個(gè)字符串不為空，如果想拼接成第三個(gè)字符串，那么必須是對(duì)應(yīng)位置的字符相等才可以，也就是第二個(gè)字符串和第三個(gè)字符串必須完全相等才可以，如果出現(xiàn)一個(gè)位置對(duì)應(yīng)字符不相等，全部白玩

四)填表順序+返回值:從上向下填寫(xiě)每一行，每一行從左向右進(jìn)行編寫(xiě)，返回值是dp[m][n]

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()+s2.length()!=s3.length()) return false;
//1.先針對(duì)初始字符串進(jìn)行預(yù)處理
        s1="-"+s1;
        s2="-"+s2;
        s3="-"+s3;
        char[] array1=s1.toCharArray();
        char[] array2=s2.toCharArray();
        char[] array3=s3.toCharArray();
//2.創(chuàng)建一個(gè)dp表,先進(jìn)行初始化
    boolean[][] dp=new boolean[array1.length][array2.length];
    dp[0][0]=true;
    for(int i=1;i<array2.length;i++){
          if(array2[i]==array3[i]) dp[0][i]=true;
          else break;
    }
    for(int j=1;j<array1.length;j++){
        if(array1[j]==array3[j]) dp[j][0]=true;
        else break;
    }
//3.填表
    for(int i=1;i<array1.length;i++){
        for(int j=1;j<array2.length;j++){
dp[i][j]=(array1[i]==array3[i+j]&&dp[i-1][j])||(array2[j]==array3[i+j]&&dp[i][j-1]);
        }
    }
//4.返回值
     return dp[array1.length-1][array2.length-1];
    }
}

思考一下這么寫(xiě)為什么不對(duì)?

二)兩個(gè)字符串刪除的最小ASCILL碼和?

712. 兩個(gè)字符串的最小ASCII刪除和 - 力扣（LeetCode）

我們可以將這個(gè)題轉(zhuǎn)化成求兩個(gè)字符串的公共子序列的ASCILL碼和最大的那一個(gè)

分析:我們求的是兩個(gè)字符串的所有公共子序列中，ASCILL碼值的最大和，運(yùn)用正難則反的思想

一)定義一個(gè)狀態(tài)表示:

dp[i][j]表示從s1字符串[0，i]區(qū)間和s2字符串[0，j]區(qū)間的所有給公共子序列中，兩個(gè)字符串的公共子序列中ASCILL碼和最大和

二)根據(jù)狀態(tài)標(biāo)識(shí)推導(dǎo)狀態(tài)轉(zhuǎn)移方程:根據(jù)最后一個(gè)位置來(lái)劃分問(wèn)題，分情況討論

要找公共子序列，是從s1里面拉出一個(gè)子序列，也需要從s2里面拉出一個(gè)子序列，判斷他們是否是公共子序列，如果是，求出它們的和，從而找到最大和

if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+s1[i]的ASCILL碼值

if(s1[i]!=s2[j]) dp[i][j]=Math.max(dp[i-1][j] dp[i][j-1],dp[i-1][j-1])

既然要求公共子序列，那么一定是包含一下幾種情況:

1)包含s1[i]，包含s2[j]:if(s1[i]==s2[j])->dp[i][j]=dp[i-1][j-1]+s1[i]的ASCILL碼

2)包含s1[i]，不包含s2[j]:dp[i][j]=dp[i][j-1](但是這個(gè)狀態(tài)標(biāo)識(shí)和狀態(tài)2是完全不對(duì)等的，這個(gè)狀態(tài)包含了包含s1[i]，不包含s2[j]和不包含s1[i]，不包含s2[j]，但是一定是不包含dp[i][j-1]

3)不包含s1[i]，包含s2[j]:dp[i][j]=dp[i-1][j]和上面同理，不包含i一定可以保證，但是也是可以不包含s2[j]的，也是可能會(huì)包括s2[j]的

4)不包含s1[i]不包含s2[j] dp[i][j]=dp[i-1][j-1]

上面的2 3情況已經(jīng)包含了第四種情況

三)初始化+填表順序+返回值:

1)引入空串:引入一行一列，第一行表示第一個(gè)字符串是空的情況，第一列表示第一個(gè)字符串是空的情況，當(dāng)有一個(gè)字符串是空的時(shí)候，根本就無(wú)法找到ASCILL碼值最大的子序列的和，其實(shí)連最長(zhǎng)公共子序列都找不到，所以他們的最長(zhǎng)公共子序列的ASCIL碼值的和就是0

2)下標(biāo)的映射關(guān)系:多加一行多加一列之后，下標(biāo)已經(jīng)統(tǒng)一向右下角移動(dòng)了一位，此時(shí)下標(biāo)一定要-1

3)填表順序:從上到下，每一行從左向右

4)返回值:兩個(gè)字符串的ASCILL總和-2*dp[m][n]

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
    int sum=0;
    for(int i=0;i<s1.length();i++){
        sum+=s1.charAt(i);
    }
    for(int i=0;i<s2.length();i++){
        sum+=s2.charAt(i);
    }
    s1="_"+s1;
    s2="_"+s2;
    char[] array1=s1.toCharArray();
    char[] array2=s2.toCharArray();
    int[][] dp=new int[array1.length][array2.length];
    for(int i=1;i<array1.length;i++){
        for(int j=1;j<array2.length;j++){
            if(array1[i]==array2[j]){
                dp[i][j]=dp[i-1][j-1]+array1[i];
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
//從包含i位置不包含j位置,不包含i位置包含j位置
            }
        }
    }
  return sum-dp[array1.length-1][array2.length-1]*2;
    }
}

三)最長(zhǎng)重復(fù)子數(shù)組:

718. 最長(zhǎng)重復(fù)子數(shù)組 - 力扣（LeetCode）

一)定義一個(gè)狀態(tài)表示:

1)我們選擇第一個(gè)數(shù)組[0，i]這段區(qū)間，我們選擇第二個(gè)數(shù)組[0，j]這段區(qū)間，我們想要的是最長(zhǎng)重復(fù)子數(shù)組，我們?cè)诘谝粋€(gè)區(qū)間內(nèi)找到所有的子數(shù)組，我們?cè)诘诙€(gè)區(qū)間內(nèi)找到所有的子數(shù)組，我們統(tǒng)計(jì)一下兩個(gè)區(qū)間內(nèi)最長(zhǎng)的重復(fù)子數(shù)組統(tǒng)計(jì)一下長(zhǎng)度即可

dp[i][j]表示第一個(gè)數(shù)組在[0，i]區(qū)間的所有子數(shù)組和[0，j]區(qū)間內(nèi)第二個(gè)數(shù)組的所有子數(shù)組中最長(zhǎng)的那一個(gè)，如果選擇[0，i]區(qū)間內(nèi)的所有子數(shù)組來(lái)研究問(wèn)題，但是這個(gè)狀態(tài)表示的范圍太大了，當(dāng)進(jìn)行推導(dǎo)下一個(gè)位置的時(shí)候，會(huì)用到前面的狀態(tài)

2)選取[0，i]區(qū)間內(nèi)的所有子數(shù)組作為研究對(duì)象，當(dāng)我們?nèi)ミM(jìn)行推導(dǎo)i+1狀態(tài)的時(shí)候，會(huì)是使用到前面這些狀態(tài)的，當(dāng)我們?cè)谶M(jìn)行推導(dǎo)i+1狀態(tài)的值的時(shí)候，想要跟在某一個(gè)子數(shù)組的后面，就必須跟在i位置的后面，所以我們?cè)谶M(jìn)行推導(dǎo)i+1狀態(tài)的時(shí)候，還需要看一下i位置子數(shù)組的狀態(tài)，但是最長(zhǎng)重復(fù)子數(shù)組可能都不包括i，可能是i-1，但是進(jìn)行研究子序列問(wèn)題的時(shí)候，i+1都是可以跟在前面的所有值的后面的，但是子數(shù)組就不行了

3)研究子數(shù)組問(wèn)題:

dp[i][j]表示nums1以i位置為結(jié)尾的所有的子數(shù)組

以及nums2以j位置為結(jié)尾的所有子數(shù)組中

dp[i][j]存的值是最長(zhǎng)重復(fù)子數(shù)組的長(zhǎng)度

二)根據(jù)狀態(tài)表示推到狀態(tài)轉(zhuǎn)移方程:

if(nums[i]==nums2[j]) dp[i][j]=dp[i-1][j-1]+1

else dp[i][j]=0

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int max=0;
        int[][] dp=new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;i++){
            for(int j=1;j<=nums2.length;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=0;
                }
                 max=Math.max(dp[i][j],max);
            }
        }
    return max;
    }
}

?五)最長(zhǎng)公共前綴:

14. 最長(zhǎng)公共前綴 - 力扣（LeetCode）

一)定義一個(gè)狀態(tài)表示:dp[i]表示以i位置為結(jié)尾的字符串?dāng)?shù)組的最長(zhǎng)公共前綴

二)根據(jù)狀態(tài)表示狀態(tài)轉(zhuǎn)移方程:

1)根據(jù)最近的一步來(lái)進(jìn)行劃分問(wèn)題，如果發(fā)現(xiàn)這個(gè)字符串所有的i位置的元素都是相等的，那么最長(zhǎng)公共前綴就是dp[i-1]+"ch"，但是如果出現(xiàn)了abcde和hhhhe這種情況，如果發(fā)現(xiàn)以i-1位置為結(jié)尾的最長(zhǎng)公共公共前綴是空，那么dp[i]也是空，雖然相等但是沒(méi)有最長(zhǎng)公共前綴

2)如果發(fā)現(xiàn)各個(gè)字符串在i位置的元素不是全部都相等，那么直接返回dp[i-1]的值

class Solution {
    public String longestCommonPrefix(String[] strs) {
        //dp[i]表示以i位置為結(jié)尾字符串?dāng)?shù)組的最長(zhǎng)公共前綴
        String minString=strs[0];
        for(String str:strs){
            if(minString.length()>=str.length()) 
              minString=str;
        }
        if(minString.equals("")) return "";
//1.先進(jìn)行初始化
       String[] dp=new String[minString.length()];
       char ch=strs[0].charAt(0);
       dp[0]=ch+"";
       for(String str:strs){
           if(str.charAt(0)!=ch){
               dp[0]="";
               break;
           }
       }
//2.進(jìn)行填表
     for(int i=1;i<minString.length();i++){
           ch=minString.charAt(i);
          for(int j=0;j<strs.length;j++){
              if(strs[j].charAt(i)!=ch){
                return dp[i-1];
              }
          }
        if(!dp[i-1].equals("")) dp[i]=dp[i-1]+ch;
        else dp[i]="";
      }
    return dp[minString.length()-1];
    }
}

class Solution {
    public String longestCommonPrefix(String[] strs) {
//1.先找到最小字符串
        String minString=strs[0];
        for(String str:strs){
            if(str.length()<minString.length()){
                minString=str;
            }
        }
    int m=minString.length();
//2.創(chuàng)建dp表
   String[] dp=new String[minString.length()+1];
   dp[0]="";
  for(int i=0;i<strs.length;i++){
      strs[i]="-"+strs[i];
  }
  minString="-"+minString;
   System.out.println(Arrays.toString(strs));
 for(int i=1;i<=m;i++){
     char ch=minString.charAt(i);
     for(String str:strs){
         if(str.charAt(i)!=ch){
             return dp[i-1];
         }
     }
     dp[i]=dp[i-1]+ch;
   }
 return dp[m];
    }
}

六)最長(zhǎng)有效括號(hào):

32. 最長(zhǎng)有效括號(hào) - 力扣（LeetCode）

解法1:動(dòng)態(tài)規(guī)劃

1)定義一個(gè)狀態(tài)標(biāo)識(shí):dp[i]表示以i位置為結(jié)尾，最長(zhǎng)有效括號(hào)的長(zhǎng)度

眾所周知，既然以i位置為結(jié)尾，最長(zhǎng)有效括號(hào)的長(zhǎng)度，那么必須是以右括號(hào)為結(jié)尾才可以是有效括號(hào)，如果單單以左括號(hào)為結(jié)尾，那么也算不上是有效括號(hào)

2)根據(jù)狀態(tài)表示推到狀態(tài)轉(zhuǎn)移方程

2.1)if(array[i]==')'&&array[i-1]=='(') dp[i]=dp[i-2]+2;

2.2)if(array[i]=="(") dp[i]=0;

2.3)if(array[i]==")"&&array[i-1]==")") dp[i]=2+dp[i-1]+dp[i-dp[i-1]-2]

class Solution {
    public int longestValidParentheses(String s) {
        char[] array=s.toCharArray();
        int[] dp=new int[array.length];
        int max=0;
//i-1不會(huì)越界,因?yàn)楫?dāng)i=0的時(shí)候,無(wú)論是左括號(hào)還是有括號(hào),最長(zhǎng)有效括號(hào)長(zhǎng)度永遠(yuǎn)是0
//這道題的初始化有點(diǎn)惡心,我們需要考慮i-2越界的情況,i-dp[i-1]-1越界的情況
//dp[i-dp[i-1]]-2越界的情況
//況且還要找array[i-dp[i-1]-1]==')'的情況
        for(int i=1;i<array.length;i++){
            if(array[i]=='(') dp[i]=0;
            else if(array[i]==')'&&array[i-1]=='('){
                dp[i]=(i-2>=0?dp[i-2]:0)+2;
            }else if(array[i]==')'&&array[i-1]==')'){
                if(i-dp[i-1]-1<0||array[i-dp[i-1]-1]==')'){
                    dp[i]=0;
                }else{
                    dp[i]=(i-dp[i-1]>=2?dp[i-dp[i-1]-2]:0)+dp[i-1]+2;
                }
            }
            max=Math.max(max,dp[i]);
        }
    System.out.println(Arrays.toString(dp));
    return max;
    }
}

解法2:棧

1)我們使用一個(gè)棧，棧里面存放的是上一個(gè)沒(méi)有進(jìn)行成功匹配的位置，首先在棧里面存放一個(gè)-1，因?yàn)槭钦f(shuō)如果括號(hào)是完全匹配的，那么根本就不存在不匹配成功的位置，此時(shí)棧里面根本沒(méi)有元素，所以要使用最后一個(gè)字符的位置減去-1

2)求一個(gè)字符串中某一段區(qū)間的長(zhǎng)度:當(dāng)前最后一個(gè)字符下標(biāo)的索引-要計(jì)算長(zhǎng)度的第一個(gè)字符的下標(biāo)的前一個(gè)位置?

具體做法是我們始終保持棧底元素為當(dāng)前已經(jīng)遍歷過(guò)的元素中，最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)，這樣的做法主要是考慮了邊界條件的處理，棧里其他元素維護(hù)左括號(hào)的下標(biāo)：

1)對(duì)于遇到的每個(gè)左括號(hào)，我們將它的下標(biāo)放入棧中
2)對(duì)于遇到的每個(gè)右括號(hào)，我們先彈出棧頂元素表示匹配了當(dāng)前右括號(hào)

3)如果彈出元素以后發(fā)現(xiàn)，如果棧為空，說(shuō)明當(dāng)前的右括號(hào)為沒(méi)有被匹配的右括號(hào)，我們將其下標(biāo)放入棧中來(lái)更新我們之前提到的，最后一個(gè)沒(méi)有被匹配的右括號(hào)的下標(biāo)
4)如果棧不為空，當(dāng)前右括號(hào)的下標(biāo)減去棧頂元素即為，以該右括號(hào)為結(jié)尾的最長(zhǎng)有效括號(hào)的長(zhǎng)度文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-605488.html

class Solution {
    public int longestValidParentheses(String s) {
        char[] array=s.toCharArray();
        Stack<Integer> stack=new Stack<>();
        stack.push(-1);
        int max=0;
        for(int i=0;i<array.length;i++){
            if(array[i]=='('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);//如果棧里面沒(méi)有元素說(shuō)明當(dāng)前沒(méi)有左括號(hào)和當(dāng)前右括號(hào)匹配,就把當(dāng)前位置的右括號(hào)放到棧里面說(shuō)明是第一個(gè)不匹配的位置
                }else{
//如果棧不為空,那么直接求出有效括號(hào)的長(zhǎng)度
                     max=Math.max(max,i-stack.peek());
                }
            }
        }
    return max;
    }
}

到了這里，關(guān)于兩個(gè)數(shù)組的dp問(wèn)題(2)--動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！