首页 > 编程语言 >算法日记 36-38day 动态规划

算法日记 36-38day 动态规划

时间：2024-12-01 15:28:38浏览次数：9  
标签：38day int 36 字符串 算法 Length 序列 dp 回文

今天把动态规划结束掉，包括子序列以及编辑距离

题目：最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

  • 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

题目分析：

        上一题求得公共子数组，这一题换成了子序列，子序列只有相对位置不改变。dp五部曲来看，dp[i,j]表示得是以i-1结尾得字符串和以j-1结尾得字符串得最长公共子序列为dp[i,j]。这里之所以写成i-1和j-1主要是为了减少初始化得麻烦。同样的，你也可以表示为i,j。上一篇得题目中写了具体得情况。

         递推公式，对于i-1和j-1来说，有两个可能，一个相同一个不同。

相同：

        既然相同，那么的dp[i,j]=dp[i-1,j-1]+1;

不同：

        如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

public class Solution {
    public int LongestCommonSubsequence(string text1, string text2) {
        int[,] dp=new int[text1.Length+1,text2.Length+1];//相当于每个字符串前面都加上了一个字符，就不用初始化列和行
        for(int i=1;i<=text1.Length;i++){
            for(int j=1;j<=text2.Length;j++)
            {
                if(text1[i-1]==text2[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];
        
    }
}

题目：不相交的线

1035. 不相交的线 - 力扣（LeetCode）

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

  •  nums1[i] == nums2[j]
  • 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

题目分析：     

        绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！

直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

 这么看来，这一题和上一题是一样得了

public class Solution {
    public int MaxUncrossedLines(int[] nums1, int[] nums2) {
        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]=Math.Max(dp[i-1,j],dp[i,j-1]);
                }
            }
        }
        return dp[nums1.Length,nums2.Length];
    }
}

题目：最大子序和

53. 最大子数组和 - 力扣（LeetCode）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。

题目分析： 

        这一题之前用贪心做过，。不过主要来看看动态规划得方法。

dp[i]:表示0-i的区间内，最大的子数组和为dp[i]

那么递推公式就很清楚了dp[i]=dp[i-1]+nums[i],不过这个值可能会变小，所以和它本身取最大。

dp[i]=max(dp[i-1]+nums[i],nums[i])

dp[i]取决于dp[i-1],所以初始化dp[0]即可

public class Solution {
    public int MaxSubArray(int[] nums) {
        int[] dp=new int[nums.Length];
        dp[0]=nums[0];
        int res=nums[0];
        for(int i=1;i<nums.Length;i++){
            dp[i]=Math.Max(dp[i-1]+nums[i],nums[i]);
            if(dp[i]>res) res=dp[i];
        }
        return res;
    }
}

题目：判断子序列

392. 判断子序列 - 力扣（LeetCode） 

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

 题目分析：

        从这一题开始就是编辑距离类型的题目了。这一题也可以使用双指针的方法，我会放在后面，主要看动态规划。

其实本质上和最长公共子序列差不多，不过多了删除这个操作。来看看它的dp

dp[i,j]:表示以i-1结尾的s和以j-1结尾的t相同子序列长度为dp[i,j]

同样的，对于i和j的字符而言，有相同和不相同两个。相同时dp[i,j]=dp[i-1,j-1]+1.

主要看不同。如果说这个字符不同，我们删去的话，dp[i,j]应该是dp[i,j-1]。取j-1的字符范围其实就是将j给删除了。

初始化    

        从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。

这里大家已经可以发现，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。

因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：


//动态规划
public class Solution {
    public bool IsSubsequence(string s, string t) {
        if(s.Length>t.Length) return false;
        //dp
        int[,] dp=new int[s.Length+1,t.Length+1];
        for(int i=1;i<=s.Length;i++){
            for(int j=1;j<=t.Length;j++){
                if(s[i-1]==t[j-1]){
                    dp[i,j]=dp[i-1,j-1]+1;
                }
                else{
                    dp[i,j]=dp[i,j-1];
                }
            }
        }
        return dp[s.Length,t.Length]==s.Length;
    }
}




//双指针
public class Solution {
    public bool IsSubsequence(string s, string t) {
        int i=0;int j=0;
        while(i<s.Length&&j<t.Length){
            if(s[i]==t[j]){
                i++;
            }
            j++;
        }
        return i==s.Length;
    }
}

题目： 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。 

题目分析： 

        动规五部曲分析。

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

那么对于s[i-1]和t[j-1]来说，有相同和不相同两种，对于相同，dp[i,j]=dp[i-1,j-1]。除此之外还有一个dp[i,j]=dp[i-1,j]。

        例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

所以递推公式为：dp[i][j] = dp[i - 1][j];

从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来，如图：，那么 dp[i][0] 和dp[0][j]是一定要初始化的。

public class Solution {
    public int NumDistinct(string s, string t) {
        int[,] dp=new int[s.Length+1,t.Length+1];
        for(int i=0;i<s.Length;i++){
            dp[i,0]=1;//t为空
        }
        for(int j=0;j<t.Length;j++){
            dp[0,j]=0;//s为空
        }
        dp[0,0]=1;//都为空
        for(int i=1;i<=s.Length;i++){
            for(int j=1;j<=t.Length;j++){
                if(s[i-1]==t[j-1]){
                    dp[i,j]=dp[i-1,j-1]+dp[i-1,j];
                }
                else{
                    dp[i,j]=dp[i-1,j];
                }
            }
        }
        return dp[s.Length,t.Length];
    }
}

题目：两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode） 

给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

 题目分析：

        两个字符串相等，那不就是公共子序列吗？这一题其实有一个简单写法，之前写最长公共子序列的时候求出两个的最长子序列，那么两个字符串把多余的部分删掉不久行了吗。这个写法就不多说了。

        dp[i,j]表示0-i的w1变成0-j的w2需要的最小步数。

对于w1[i-1]==w2[j-1]的情况，dp[i,j]=dp[i-1,j-1]。不需要删除

对于不相同的情况，删除可以有三中选择，

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

public class Solution {
    public int MinDistance(string word1, string word2) {
    //以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
        int[,] dp=new int[word1.Length+1,word2.Length+1];
        for(int i=1;i<=word1.Length;i++){
            dp[i,0]=i;
        }
        for(int j=1;j<=word2.Length;j++){
            dp[0,j]=j;
        }
        for(int i=1;i<=word1.Length;i++){
            for(int j=1;j<=word2.Length;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i,j]=dp[i-1,j-1];
                }
                else{
                //dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
                //dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2，
                //所以递推公式可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                    dp[i,j]=Math.Min(dp[i-1,j]+1,dp[i,j-1]+1);
                }
            }
        }
        return dp[word1.Length,word2.Length];
    }
}

 题目：编辑距离

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数  。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
 题目分析：

        上一题只有删除一种操作，而现在有插入和替换，删除3种操作。其实大差不差，主要看dp的公式。

对于删除而言，dp[i,j]=min(dp[i-1,j],dp[i,j-1]) 具体分析看上一题。

对于插入而言，比如ab,a。实际上对a添加一个b等同于对ab删除一个b,两个的操作步数是一样的，意味着我们不需要取考虑插入，他和删除完全一样

对于替换，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。

可以回顾一下，if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

初始化部分和之前一样

public class Solution {
    public int MinDistance(string word1, string word2) {
        int[,] dp=new int[word1.Length+1,word2.Length+1];
        for(int i=1;i<=word1.Length;i++){
            dp[i,0]=i;
        }
        for(int j=1;j<=word2.Length;j++){
            dp[0,j]=j;
        }

        for(int i=1;i<=word1.Length;i++){
            for(int j=1;j<=word2.Length;j++){
                if(word1[i-1]==word2[j-1]){
                    dp[i,j]=dp[i-1,j-1];
                }
                else{
                    dp[i,j]=Math.Min(Math.Min(dp[i-1,j]+1,dp[i,j-1]+1),dp[i-1,j-1]+1);
                }
            }
        }
        return dp[word1.Length,word2.Length];
    }
}

题目：回文字串

647. 回文子串 - 力扣（LeetCode）

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

题目分析： 

         如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。

        那么，对于一个回文串来说，他是什么样的呢？

 

对于cbabc而言，中间部分bab是回文串，那整体呢？是不是取决于边界。

此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串下标范围[i,j]）是否回文，依赖于，子字符串（下标范围[i + 1, j - 1]）） 是否是回文。

所以我们的dp定义为布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

  • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i 与 j相差为1，例如aa，也是回文子串
  • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true

初始化为false即可，这里不用多说

那么遍历顺序呢？

从递推公式可以看出来情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

所以我们的遍历顺序一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

public class Solution {
    public int CountSubstrings(string s) {
        bool[,] dp=new bool[s.Length,s.Length];
        int res=0;
        for(int i=s.Length-1;i>=0;i--){
            for(int j=i;j<s.Length;j++){
                if(s[i]==s[j]){
                    if(j-i<=1){
                        res++;
                        dp[i,j]=true;
                    }
                    else if(dp[i+1,j-1]){
                        res++;
                        dp[i,j]=true;
                    }
                }
            }
        }
        return res;
    }
}

 题目：最长回文子序列

 516. 最长回文子序列 - 力扣（LeetCode）

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

 题目分析：

        又是子序列。还是五部曲。

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

        如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

 

        如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

        加入s[j]的回文子序列长度为dp[i + 1][j]。

        加入s[i]的回文子序列长度为dp[i][j - 1]。

        那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

dp数组如何初始化

        首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

        所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

        其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖

public class Solution {
    public int LongestPalindromeSubseq(string s) {
        //字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
        int[,] dp=new int[s.Length,s.Length];
        for(int i=0;i<s.Length;i++){
            dp[i,i]=1;
        }
        for (int i = s.Length - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.Length; j++) {
                if (s[i] == s[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];
    }
}

 

至此，动态规划的题目全部完结。

总结

动规五部曲分别为：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

 动态规划解决的问题包括基本问题，背包问题，股票问题，子序列问题，打家劫舍等等。

 

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)

已刷题目：125

标签：38day,int,36,字符串,算法,Length,序列,dp,回文
From： https://blog.csdn.net/weixin_70808146/article/details/144168943

相关文章

  • P11361 [NOIP2024] 编辑字符串
    题目大意详细题目传送门两个\(01\)串，可以对两个串中任意相邻的字符进行交换，没有代价可以进行任意多次。可是两个串有的位置的字符是定死的，无法被交换，求任意次操作后最多让两个串的多少个位置\(01\)相等。即\(\sum[a_i=b_i]\)。\(n\leq10^5\)思路首先根据冒泡排序的性......
  • 洛谷P11361 [NOIP2024] 编辑字符串
    ProblemSolve首先任意更换相邻元素任意次等同于在可交换范围内随便移动这题是求最优解，直观想到DP和贪心，但是容易反应过来本题DP的话很难做到无后效性，且状态较多，故尝试贪心不难发现，我们从左往右遍历的某个时刻进行交换后所得到的局部最优解总是答案的一种方案的一部分原因......
  • MATLAB实现WOA-BP鲸鱼优化算法优化BP神经网络多输入单输出回归预测（多指标，多图）
    目录MATLAB实现WOA-BP鲸鱼优化算法优化BP神经网络多输入单输出回归预测（多指标，多图）    1项目背景介绍...1项目目标与意义...2项目挑战...4项目特点与创新...5项目模型架构...6项目模型描述及代码示例...7项目部署与应用...12项目扩展...15项目应该注意事......
  • MATLAB实现SA-BP模拟退火算法优化BP神经网络多输入单输出回归预测（多指标，多图）
    目录MATLAB实现TA-BP模拟退火算法优化BP神经网络多输入单输出回归预测（多指标，多图）...1项目背景介绍...1项目目标与意义...2项目挑战...3项目特点与创新...4项目应用领域...5项目效果预测图程序设计...6项目模型架构...7项目模型算法流程图...7详细模型描述及......
  • MATLAB实现基于PSO-LSSVM-Adaboost粒子群算法优化最小二乘支持向量机结合AdaBoost多输
    目录MATLAB实现基于PTO-LTTVM-Adaboott粒子群算法优化最小二乘支持向量机结合AdaBoott多输入单输出回归预测    2项目背景介绍...2背景...2项目目标与意义...2目标...2意义...2项目挑战...3项目特点与创新...3项目应用领域...3项目效果预测图程序设计........
  • 【机器学习】探索机器学习决策树算法的奥秘
    决策树前言基本概念常见的决策树算法ID3算法C4.5算法CART算法决策树的优缺点应用场景决策树的可视化总结前言在当今这个数据驱动的时代，机器学习作为数据分析与预测的利器，正以前所未有的速度改变着我们的生活和工作方式。在众多机器学习算法中，决策树算法以其直观......
  • 洛谷 P1036 [NOIP2002 普及组] 选数 C语言
    题目：https://www.luogu.com.cn/problem/P1036题目描述已知 nn 个整数 x1,x2,⋯ ,xn，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k=3，4 个整数分别为 3,7,12,19时，可得全部的组合与它们的和为：3+7+12=223+7+19=297+12......
  • 【老生谈算法】matlab实现融合黄金正弦的改进粒子群算法GSPSO在无人机避障三维航迹规
    MATLAB实现融合黄金正弦的改进粒子群算法GSPSO在无人机避障三维航迹规划中的应用1、全套下载：本项目完整讲解和全套实现源码见下资源，有需要的朋友可以点击进行下载说明文档（点击下载）本算法文档【老生谈算法】matlab实现融合黄金正弦的改进粒子群算法GSPSO在无人机避障三维......
  • 【老生谈算法】matlab实现哈里斯鹰算法在复杂山地环境下无人机三维路径规划中的应用研
    MATLAB实现哈里斯鹰算法在复杂山地环境下无人机三维路径规划中的应用研究1、全套下载：本项目完整讲解和全套实现源码见下资源，有需要的朋友可以点击进行下载说明文档（点击下载）本算法文档【老生谈算法】matlab实现哈里斯鹰算法在复杂山地环境下无人机三维路径规划中的应用研......
  • 双指针算法6
    进度：28/100原题1：给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。原题2：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。原题3：假设你是一位很棒的家长，想要......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99