算法套路学习笔记(第二章) 动态规划系列 2.4-2.82.4 最优子结构以及dp遍历方向2.5 经典动态规划问题-最长公共子序列2.6 经典动态规划问题-编辑距离2.7 子序列问题-最长回文子序列2.8 状态压缩动态规划

83 阅读 0 评论 55 点赞

我是靠谱客的博主闪闪便当，最近开发中收集的这篇文章主要介绍算法套路学习笔记(第二章) 动态规划系列 2.4-2.82.4 最优子结构以及dp遍历方向2.5 经典动态规划问题-最长公共子序列2.6 经典动态规划问题-编辑距离2.7 子序列问题-最长回文子序列2.8 状态压缩动态规划，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2.4 最优子结构以及dp遍历方向

关键是要学习 最优子结构 以及和 动态规划 以及dp数组的遍历方向

2.4.1 什么叫最优子结构

可以从子问题的最优结果推出更大规模问题的最优结果,这就是最优子结构问题,如果要满足最优子结构问题,那么就必须要满足子问题之间相互独立的条件。

如果有存在不满足最优子结构问题的，那么可以对该问题进行转换，可以通过一定的数学推理变换将不具有最优子结构的问题转换为具有最优子结构的问题。

例如说：要求全校所有人的最大分数差,不能通过求取每班的最大分数差来求得,这种就不是直观的最优子结构问题，但是我们可以通过转换为其他具有最优子结构的而且该问题求解得出的参量与数据是有一定关系的。
比如说我要求全校所有人的最大分数差，虽然没办法用每个班的最大分数差来算，但是我可以求出每个班的最大分数和每个班的最小分数来求出每个班的最大分数差
这就是一种最基本的转换思想当要求最大差值的时候,可以先求各项的极值,再以求出来的各项的极值求出来最大差值即可,那么这就给了我一种思路,如果以后碰到最值的问题,如果穷举暴力的时间复杂度过不了的话,那么就往动态规划方面走

2.4.2 如何确定遍历的方向?

1.遍历的过程中,所需的状态必须是已经计算出来的了
2.遍历的终点必须是存储结果的那个位置(这个对于以nums[i]为结尾的那道题来说是不确定的,但是可以通过状态压缩,简化算法来达到这个目的)

2.5 经典动态规划问题-最长公共子序列

第一步,确定dp数组的定义
对于道题而言,dp数组应当定义为dp[i][j],其含义为:对于str1的前i个字符[0,.....,i-1]和str2的前j个字符[0,...,j-1]个字符的最长公共子序列长度为 dp[i][j]
第二步,定义base-case
basecase只需要考虑最简单的、最显然的情况即可,首先对于str1如果用的是前0个字符的话,那么LCS长度肯定是0,这就是一种最简单的情况,因此basecase就是
dp[0][0...j]=dp[0,...,i][0]=0
第三步,写出状态转移方程
状态转移方程实际是就是列举在枚举过程中的选择过程,首先我们需要确定的是,在本问题中的选择是什么?对于在遍历str1和str2的过程中,我们在选择前i个字符和选择前j个字符的时候,应该怎么选才能选出来公共子序列?那么也就是在遍历第i个字符的时候,假如这时候j指针指向的字符与i指向的字符是一样的,那么就认为是最长公共子序列
那么也就是

if(str1[i].equals(str2[j])){
	dp[i][j]=dp[i-1][j-1]+1;//将该字符加入到LCS中,计数++
}else{
	dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
	//然后既然我str1[i]和str2[j]已经不是相同的字符了,那么就应该要推算了
	//是选择str1[i-1],str2[j]、str1[i],str2[j-1]、还是str1[i-1],str2[j-1]的最大公共子序列?
	//这个选择应该是要根据长度来的,但是我们可以排除掉dp[i-1][j-1]
	//因为我们在逻辑上,如果多一个字符选择,那么就代表着我的最大长度可能更长
}

经过以上三步,基本上就能够确定代码的写法了

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

    }
}

一般地,还可以写出来dp函数,思路是完全一致的,同时为了避免超时,可以做备忘录

class Solution {
public:
    string str1,str2;
    int m[1000+5][1000+5];
    int dp(int i,int j){
        if(i==-1 || j==-1){
            return 0;
        }
        if(str1[i] == str2 [j]){
            if(m[i][j] == -1){
                m[i][j] = dp(i-1,j-1)+1;
            }
            return m[i][j];
        }else{
            if(m[i][j] == -1){
                m[i][j] =  std::max(dp(i-1,j),dp(i,j-1));
            }
            return m[i][j];
            

        }
    }


    int longestCommonSubsequence(string text1, string text2) {
        str1 = text1;str2 = text2;
        for(int i=0;i<=str1.size();i++){
            for(int j=0;j<=str2.size();j++){
                m[i][j]=-1;
            }
        }
        return dp(str1.size()-1,str2.size()-1);
    }
};

2.6 经典动态规划问题-编辑距离

问题描述:可以对一个字符串进行三种操作，插入一个字符，删除一个字符，替换一个字符
首先理解下题意以及主观上来解释一下题意，我们来举个例子吧:
radple和apple，我们人手来算一次:
首先i和j指针指向字符串的最后一位，开始计算:

首先是e和e，对上了，i和j指针同时向左移动
接着是l和l，对上了，i和j指针同时向左移动
接着是p和p，对上来，i和j指针同时向左移动
接着是d和p，没有对上，这时候就存在三个选择,1.插入一个字符2.删除一个字符3.替换一个字符
这里说明一下，最终的目标是为了使得s1和s2相同，由于从s1变到s2和s2变到s1的所需要的变化次数都是一样的
我们规定让s1去匹配s2，对于匹配不上的情况，我们有三种选择
1.插入操作，我们向s1中不匹配的字母后插入一个字母，然后s2的字符串遍历指针向前移动一位了，继续匹配
2.删除操作，我们将s1的那个不匹配的字母删除掉,i前进一位,j指针不变
3.替换操作,i和j指针同时前进一位

解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的最后，然后一步步往前走，缩小问题的规模
对于这道题，我们使用常规的动态规划套路进行分析

确定dp数组含义:s1[0...i]和s2[0...j]的最小编辑距离是dp(i,j)
对于这道题而言，比较复杂，我们可以先从dp数组开始写起
确定base-case:i指针走完s1或者j指针走完s2,这时候就可以直接返回另一个字符串剩下的长度
确定状态转移方程:对于每对字符s1[i]和s2[j]，可以有4种操作,所谓状态，就是算法在推进过程中会变化的量，显然这里就是指针i和指针j的位置,选择流是对于每一种状态，可以做出的选择。如下四种操作

if(s1[i] == s2[j]){
    //此时不需要调整
    skip();
    i--;j--;
}else{
    三选一:
    insert();
    delete();
    replace();
}

根据以上分析,可以先写出代码

import org.junit.Test;

public class MinDistance {
    //定义dp函数 dp(i int,j int) int
    //含义是第s1的[0,i-1]的串变成s2的[0,j-1]所需要的最小次数
    private String s1;
    private String s2;
    private int dp(int i,int j){
        //base-case:如果i走完了s1,而j还没走完s2,就可以直接返回另一个字符串剩下的长度了
        if(i==-1){
            return j+1;
        }
        if(j==-1){
            return i+1;
        }
        //做选择
        if(s1.charAt(i) == s2.charAt(j)){
            //直接返回本次计算的结果
            return dp(i-1,j-1);
        }
        //否则就做选择
        //我们来看看插入、删除、替换，在dp函数里面是分别是如何表示的
        //我们以下的表示法是基于s1->s2的过程来写的
        //插入:dp(i,j-1)+1:首先+1就代表着要消耗一次修改次数,然后我们来判断指针如何运动,由于是插入的,因此j对应的字符
        //就被对应上了,而i还没有被匹配,因此i不动,j-1
        //删除:dp(i-1,j)+1与插入是同理的,由于是删除s1中的字符,就相当于是j对应的字符还没有被对应上,而i对应的字符被省略,视而不见,因此i-1了
        //替换:dp(i-1,j-1)+1由于是从s1变成s2,因此就是修改s1中的第i位字符,使得与s2中的第j位字符所对应,这时候两位都匹配上了,i-1,j-1
        return Math.min(Math.min(dp(i-1,j)+1,dp(i,j-1)+1),dp(i-1,j-1)+1);
    }

    public int minDistance(String s1,String s2){
        this.s1 = s1;
        this.s2 = s2;
        //算法起点是字符串的最末尾
        return dp(s1.length()-1,s2.length()-1);
    }

    @Test
    public void test(){
        System.out.println(minDistance("horse","ros"));
    }


}

代码非常简洁,dp函数的定义也比较清晰，但是本解法存在着重叠子问题(重复计算)的问题,当数据量一大就可能导致TLE了，怎么看出来的呢?首先对于子问题dp(i-1,j-1),可以从dp(i,j)->(通过替换)->dp(i-1,j-1),也可以通过dp(i,j)->(先插入)->(再删除)->dp(i-1,j-1),怎么解决呢?很简单,备忘录。我们设置一个map,当map中有着我们想要的键值对的时候，就直接取出来用，不要再去dp里面计算，因为之前已经算过一次了

class Solution {
     //定义dp函数 dp(i int,j int) int
    //含义是第s1的[0,i]的串变成s2的[0,j]所需要的最小次数
    private String s1;
    private String s2;
    private int[][] m;
    private int dp(int i,int j){
        //base-case:如果i走完了s1,而j还没走完s2,就可以直接返回另一个字符串剩下的长度了
        if(i==-1){
            return j+1;
        }
        if(j==-1){
            return i+1;
        }
        //做选择
        if(m[i][j]!=-1){
            return m[i][j];
        }
        if(s1.charAt(i) == s2.charAt(j)){
            //直接返回本次计算的结果
            if(m[i][j] == -1){
                m[i][j] = dp(i-1,j-1);
            }
            return m[i][j];
        }
        //否则就做选择
        //我们来看看插入、删除、替换，在dp函数里面是分别是如何表示的
        //我们以下的表示法是基于s1->s2的过程来写的
        //插入:dp(i,j-1)+1:首先+1就代表着要消耗一次修改次数,然后我们来判断指针如何运动,由于是插入的,因此j对应的字符
        //就被对应上了,而i还没有被匹配,因此i不动,j-1
        //删除:dp(i-1,j)+1与插入是同理的,由于是删除s1中的字符,就相当于是j对应的字符还没有被对应上,而i对应的字符被省略,视而不见,因此i-1了
        //替换:dp(i-1,j-1)+1由于是从s1变成s2,因此就是修改s1中的第i位字符,使得与s2中的第j位字符所对应,这时候两位都匹配上了,i-1,j-1
        if(m[i][j] == -1){
            m[i][j] = Math.min(Math.min(dp(i-1,j)+1,dp(i,j-1)+1),dp(i-1,j-1)+1);
        }
        return m[i][j];
    }

    public int minDistance(String s1,String s2){
        this.s1 = s1;
        this.s2 = s2;
        m = new int[s1.length()+5][s2.length()+5];
        for(int x = 0;x<s1.length();x++){
            for(int y = 0;y<s2.length();y++){
                m[x][y] = -1;
            }
        }
        //算法起点是字符串的最末尾
        return dp(s1.length()-1,s2.length()-1);
    }
}

DP table的解法

dp()函数更多的是为我们提供直观的算法思路,下面介绍如何使用DPTable来进行解题

int dp(int i,int j)//返回的是s1[0...i]和s2[0...j]的最小编辑距离
dp[i][j]//存储的是s1[0...i-1]和s2[0...j-1]的最小编辑距离

同样的的，我们三步走来分析本题如何做

确定dp数组含义:dp[i][j]:s1[0…i-1]和s2[0…j-1]的最小编辑距离
确定base-case:base-case就是当有其中一个指针走完的时候,可以直接得到从其中一个字符串变成另外一个字符串时的长度
确定状态转移方程
- 状态:算法推算过程中,会发生变化的量,也就是指针移动量
- 选择:dp[i][j]的值的变化(skip(),insert(),delete(),update())
依照上述思路编写代码

    public int minDistance(String word1, String word2) {
        //1.定义dp数组
        int[][] dp = new int[word1.length()+5][word2.length()+5];
        //2.写出base-case
        //当j走完的时候其下标是-1,但是java中下标是没有-1,因此我们将指针加上一个偏移量(+1)
        //for(int i = 0;i<word1.length();i++){
            //dp[i][0] = i-1;
        //}
        //变成:
        for(int i = 1;i<=word1.length();i++){//当j已经走到了-1的据欧
            dp[i][0] = i;
        }
        for(int j = 1;j<=word2.length();j++){
            dp[0][j] = j;
        }
        //3.穷举所有选择,根据状态转移方程编码
        //等号以及开始下标怎么确定呢?
        //我们来看:首先开始下标是要根据base-case来确定的,推算的起点应该比base-case多一个级别
        //比如说base-case确定的是下标为0的所有数字,那么我开始推算就应该从0+1(不知道的地方)开始推算
        //等号的话就是我最终答案包含在哪个范围之内,我要用哪些数据
        //我最终的答案都是要用word.length()-1这个数据的来推算的,所以我应该在计算时把=包含进去
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else {
                    dp[i][j] = Math.min(Math.min(dp[i-1][j-1]+1,dp[i-1][j]+1),dp[i][j-1]+1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

2.7 子序列问题-最长回文子序列

一般来说，一旦涉及到子序列和最值，几乎可以肯定，考察的是动态规划技巧，时间复杂度一般都是O(n^2)

首先给出dp的思路模板

//1.基于1维的dp数组
int n = array.length();
int[] dp = new int[n];
for(int i = 1 ;i<n;i++){
    for(int j = 0;j<i;j++){
        dp[i] = max(dp[i],dp[j]+...);
    }
}

在这个思路中,dp数组的定义是在子数组array[0…i]中,以array[i]为结尾的最长递增子序列的长度为dp[i]

//2.基于2为的dp数组
int n= array.length();
int[][] dp = new int[n][n];
for(int i = 0;i<n;i++){
    for(int j = 0;j<n;j++){
        if(arr[i] == arr[j]){
            dp[i][j] = dp[i][j] + ...
        }else{
            dp[i][j] = 最值(...)
        }
    }
}

这种思路运用得比较多，应用场景主要是涉及到两个字符串/数组的子序列中，比如说"最长公共子序列"和"编辑距离"等，本思路中的dp数组含义可以分为"只涉及到一个字符串"、"涉及两个字符串"两个情况。

涉及两个字符串/数组时
- 在子数组arr1[0…i]和子数组arr2[0…j]中,要求的子序列(最长公共子序列)长度为dp[i][j]
只设计一个字符串/数组时
- 在子数组arr[i…j]中,要求的子序列的长度为dp[i][j]

我们试着来解一下最长回文子序列这道题

确定dp数组含义:dp[i][j]指的是arr[i...j]之间其回文子序列长度为dp[i][j]
确定base-case：当i==j的时候,这时候肯定是一个回文串,而且回文串长度是1,那么也就是dp[i][j] = 1
确定状态转移方程:dp[i][j] = dp[i-1][j+1]+2 or dp[i][j] = max(dp[i-1][j],dp[i][j+1])
- 状态:i,j指针的值,最终状态是[0…n-1],因此算法返回的值是dp[0][n-1]
- 选择:是否将i(j)选入截取的最大子序列的范围内?
- 归纳思路:由局部到整体,因为我们已经得到了一个最基本的子序列的回文长度，比如说我知道了dp[2][2] = 1,那么我是否能够通过dp[2][2]来得到dp[1][3]的值呢?这取决于s[1]和s[3]的值,如果说有s[1]==s[3],那么dp[2-1][2+1]+=2,我们将2分别替换为i,j,就得到公式dp[i][j] = dp[i+1][j-1]+2,如果说有s[1]!=s[3],这时候为了取得最长的回文子序列，要做选择,也就是做max(dp[i+1][j],dp[i][j-1])

    public int longestPalindromeSubseq(String s) {
        //对于动态规划问题,我们三步走
        //1.定义dp数组,dp[i][j]指的是arr[i...j]之间其回文子序列长度为dp[i][j]
        int[][] dp = new int[s.length()+5][s.length()+5];
        //2.写出base-case
        for(int i = 0 ;i<s.length();i++){
            dp[i][i] = 1;
        }
        //3.写出状态转移方程
        for(int i = s.length()-2;i>=0;i--){
            for(int j = i+1;j<s.length();j++){
                if(s.charAt(i)== s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }

2.8 状态压缩动态规划

能够使用状态压缩技巧的动态规划都是二维的DP问题，观察状态转移方程，如果计算dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩的技巧，将二维的dp数组转化为一维。
如何解析和dp[i][j]相邻的状态?
- 我们以最长回文子序列问题为例，来看dp[i][j]是如何转移的,其转移均是由dp[i+1][j-1]、dp[i][j-1]、dp[i+1][j]这三个状态转换得来的，这就叫做与dp[i][j]相邻
状态压缩的核心思路就是将二维数组降维投影到一维数组
- 难点:对于dp[i][j-1]和dp[i+1][j-1]而言,这两个状态处于同一列，而一维数组中只能容纳下一个，那么当计算dp[i][j]的时候，其中必然会有一个被另外一个所覆盖,如何处理？

以最长回文子序列为例,讲解应该如何做这个事情

        //3.写出状态转移方程
        for(int i = s.length()-2;i>=0;i--){
            for(int j = i+1;j<s.length();j++){
                if(s.charAt(i)== s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

想要把二维dp数组压缩成一维，一般来说是把第一个维度，也就是i这个维度去掉，只剩下j这个维度，压缩之后的一维dp数组就是之前二维dp数组的dp[i][...]那一行

        //3.写出状态转移方程
        for(int i = s.length()-2;i>=0;i--){
            for(int j = i+1;j<s.length();j++){
                //在这里,一维dp数组中的数是多少?
                if(s.charAt(i)== s.charAt(j)){
                    dp[j] = dp[j-1] +2 ;
                }else{
                    dp[i][j] = Math.max(dp[j],dp[j-1]);
                }
            }
        }

上述代码的一维dp数组值能表示二维dp数组的一行dp[i][...],如何才能得到dp[i+1][j-1]、dp[i][j-1]、dp[i+1][j]这几个必要的值,进行状态转移呢?
在代码注释的位置，将要进行状态转移,更新dp[j],要来思考两个问题
- 对dp[j]赋新值之前，dp[j]对应着二维dp数组中的什么位置?
  - dp[j]的值就是外层for循环上一次迭代所计算出来的值，也就是对应二维数组里边dp[i+1][j]的位置
- dp[j-1]对应着dp数组的什么位置?
  - dp[j-1]的值就是内层for循环上一次迭代算出来的值，也就是对应二维dp数组中dp[i][j-1]的位置
如何得到dp[i+1][j-1]?
- 这个状态不能直接从dp数组中得到
- 由下标的转移量可知，for循环遍历i和j的顺序为从左到右，从下到上，所以在更新一维dp数组时，dp[i+1][j-1]将会被dp[i][j-1]所覆盖掉
- 如何解决?很简单，在它被覆盖之前用一个临时变量temp把它存起来，并把这个变量的值保留到计算dp[i][j]的时候

        //3.写出状态转移方程
        for(int i = s.length()-2;i>=0;i--){
            //存储dp[i][j-1]的值即可
            int pre = 0;
            for(int j = i+1;j<s.length();j++){
                int temp = dp[j];
                if(s.charAt(i)== s.charAt(j)){
                    dp[j] = pre+2;
                }else{
                    dp[i][j] = Math.max(dp[j],dp[j-1]);
                }
                //到下一轮循环,pre就是dp[i+1][j-1]了
                pre = temp;
            }
        }

解析:我们假设现在i=5,j=7而且s[5]=s[7]

//进入到这个if里面
if(s[5] == s[7]){
    //dp[5][7] = dp[i+1][j-1]+2;
    dp[7] = pre+2;
}

pre变量->内层for循环上一次迭代的temp值->dp[j-1]->dp[6]->二维dp数组中的dp[i+1][6] = dp[6][6]
dp[i+1][j-1] = dp[6][6]

    public int longestPalindromeSubseq(String s) {
        int[] dp = new int[s.length()+5];
        for(int i = 0 ;i<=s.length();i++){
            dp[i] = 1;
        }
        for(int i = s.length()-2;i>=0;i--){
            int pre = 0;
            for(int j = i+1;j<s.length();j++){
                int temp = dp[j];
                if(s.charAt(i) == s.charAt(j)){
                    dp[j] = pre+2;
                }else{
                    dp[j] = Math.max(dp[j],dp[j-1]);
                }
                pre = temp;
            }
        }
        return dp[s.length()-1];
    }