算法专题:线性DP

这篇具有很好参考价值的文章主要介绍了算法专题:线性DP。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

参考练习习题总集

10. 正则表达式匹配

第一道题就是困难题让我很难蚌,真是磨人啊。

class Solution {
public:
    bool isMatch(string s, string p) {
        int * * matrix=new int * [p.size()+1];
        for (int i=0;i<p.size()+1;i++)
        {
            matrix[i]=new int [s.size()+1];
            for (int j=0;j<s.size()+1;j++)
                matrix[i][j]=0;
        }
        matrix[0][0]=1;
        for (int i=1;i<p.size();i+=2)
        {
            if (p[i]=='*') matrix[i+1][0]=1;
            else break;
        }
        for (int i=1;i<p.size()+1;i++)
            for (int j=1;j<s.size()+1;j++)
                if (s[j-1]==p[i-1] or p[i-1]=='.')
                {
                    if (matrix[i-1][j-1]==1)
                    {
                        matrix[i][j]=1;
                    }
                }
                else if (p[i-1]=='*')
                {
                    if (matrix[i-2][j]==1)
                    {
                        matrix[i][j]=1;continue;
                    }
                    if (matrix[i][j-1]==1 and (s[j-1]==p[i-2] or p[i-2]=='.'))
                        matrix[i][j]=1;
                }
        bool result=matrix[p.size()][s.size()];
        for (int i=0;i<p.size()+1;i++)
            delete [] matrix[i];
        return result;
    }
};

44. 通配符匹配

嗨嗨嗨,思想差不多的,又水一道困难题。

class Solution {
public:
    bool isMatch(string s, string p) {
        int len1=s.size(),len2=p.size();
        int * * matrix=new int * [len2+1];
        for (int i=0;i<len2+1;i++)
        {
            matrix[i]=new int [len1+1];
            for (int j=0;j<len1+1;j++)
                matrix[i][j]=0;
        }
        matrix[0][0]=1;
        for (int i=0;i<len2;i++)
            if (p[i]=='*') matrix[i+1][0]=1;
            else break;
        for (int i=1;i<len2+1;i++)
            for (int j=1;j<len1+1;j++)
            {
                if (s[j-1]==p[i-1] or p[i-1]=='?')
                {
                    if (matrix[i-1][j-1]==1)
                        matrix[i][j]=1;
                }
                else if (p[i-1]=='*')
                {
                    if (matrix[i-1][j]==1)
                    {
                        matrix[i][j]=1;continue;
                    }
                    if (matrix[i-1][j-1]==1 or matrix[i][j-1]==1)
                        matrix[i][j]=1;
                }
            }
        bool result=matrix[len2][len1];
        for (int i=0;i<len2+1;i++)
            delete [] matrix[i];
        return result;
    }
};

45. 跳跃游戏 II

记忆化搜索。这里的记忆化搜索本质就是线性DP。做这道题时真是气死我了,一开始明明记着长度为0的时候需要特判,但是后面做着做着就忘了加上去,交了一次又发现if (temp[i]!=0) return temp[i];没有加上去,连着犯了两次低级错误。

class Solution {
public:
    vector<int> lb;vector<int> temp;
    int jump(vector<int>& nums) {
        if (nums.size()==1) return 0;
        lb=nums;temp.resize(nums.size(),0);
        return dfs(0);
    }
    int dfs(int i)
    {
        if (temp[i]!=0) return temp[i];
        if (i+lb[i]>=lb.size()-1) return 1;
        int result=1e4-1;
        for (int j=lb[i];j>=1;j--)
        {
            int result_temp=dfs(i+j)+1;
            if (result_temp<result)
                result=result_temp;
        }
        temp[i]=result;
        return result;
    }
};

53. 最大子数组和(LCR 161 连续天数的最高销售额)

前缀和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int * lb=new int [nums.size()+1];lb[0]=0;
        for (int i=1;i<nums.size()+1;i++)
            lb[i]=lb[i-1]+nums[i-1];
        int min_value=0,result=INT_MIN;
        for (int i=1;i<nums.size()+1;i++)
        {
            int result_temp=lb[i]-min_value;
            if (result_temp>result) result=result_temp;
            if (lb[i]<min_value) min_value=lb[i];
        }
        delete [] lb;
        return result;
    }
};

线性DP

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        for (int i=1;i<nums.size();i++)
            if (nums[i-1]>0)
                nums[i]+=nums[i-1];
        int result=INT_MIN;
        for (int i=0;i<nums.size();i++)
            if (nums[i]>result)
                result=nums[i];
        return result;
    }
};

91. 解码方法

class Solution {
public:
    int numDecodings(string s) {
        if (s[0]=='0') return 0;
        int * lb=new int [s.size()+1];
        lb[0]=0;lb[1]=1;
        for (int i=2;i<s.size()+1;i++)
            if (s[i-1]=='0')
            {
                if (s[i-2]=='1' or s[i-2]=='2')
                    lb[i]=max(lb[i-2],1);
                else return 0;
            }
            else
            {
                lb[i]=lb[i-1];
                if (s[i-2]=='1' or (s[i-2]=='2' and s[i-1]<='6'))
                    lb[i]+=max(lb[i-2],1);
            }
        int result=lb[s.size()];
        delete [] lb;
        return result;
    }
};

97. 交错字符串

记忆化搜索

class Solution {
public:
    string string1,string2,string3;vector<vector<int>> temp;
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size()+s2.size()!=s3.size()) return false;
        string1=s1;string2=s2;string3=s3;temp.resize(s1.size()+1,vector<int> (s2.size()+1,0));
        return func(0,0);
    }
    bool func(int l1,int l2)
    {
        if (l1==string1.size() and l2==string2.size()) return true;
        if (temp[l1][l2]!=0) return temp[l1][l2]==1;
        bool result=false;
        if (l1<string1.size() and string1[l1]==string3[l1+l2])
            result|=func(l1+1,l2);
        if (l2<string2.size() and string2[l2]==string3[l1+l2])
            result|=func(l1,l2+1);
        temp[l1][l2]=result?1:-1;
        return result;
    }
};

线性DP

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s1.size()+s2.size()!=s3.size()) return false;
        int * * matrix=new int * [s1.size()+1];
        for (int i=0;i<s1.size()+1;i++)
        {
            matrix[i]=new int [s2.size()+1];
            for (int j=0;j<s2.size()+1;j++)
                matrix[i][j]=0;
        }
        queue<pair<int,int>> dl;dl.push(make_pair(0,0));
        while (1)
        {
            queue<pair<int,int>> temp;
            if (dl.front().first+1<=s1.size())
                temp.push(make_pair(dl.front().first+1,dl.front().second));
            while (!dl.empty())
            {
                int x=dl.front().first,y=dl.front().second;
                if (x==0 and y==0) matrix[x][y]=1;
                else if (x==0)
                {
                    if (matrix[x][y-1]==1 and s2[y-1]==s3[y-1])
                        matrix[x][y]=1;
                }
                else if (y==0)
                {
                    if (matrix[x-1][y]==1 and s1[x-1]==s3[x-1])
                        matrix[x][y]=1;
                }
                else
                {
                    if ((matrix[x][y-1]==1 and s2[y-1]==s3[x+y-1]) or (matrix[x-1][y]==1 and s1[x-1]==s3[x+y-1]))
                        matrix[x][y]=1;
                }
                if (dl.front().second+1<=s2.size())
                    temp.push(make_pair(dl.front().first,dl.front().second+1));
                dl.pop();
            }
            if (temp.empty()) break;
            dl=temp;
        }
        bool result=matrix[s1.size()][s2.size()];
        for (int i=0;i<s1.size()+1;i++)
            delete [] matrix[i];
        return result;
    }
};

115. 不同的子序列

wtql,感觉神功大成了。

class Solution {
public:
    int numDistinct(string s, string t) {
        int mod=1e9+7;
        int * * matrix=new int * [s.size()+1];
        for (int i=0;i<s.size()+1;i++)
        {
            matrix[i]=new int [t.size()+1];
            for (int j=0;j<t.size()+1;j++)
                matrix[i][j]=0;
        }
        for (int i=1;i<s.size()+1;i++)
            for (int j=1;j<t.size()+1;j++)
                if (s[i-1]==t[j-1])
                {
                    matrix[i][j]=(matrix[i][j]+matrix[i-1][j])%mod;
                    matrix[i][j]=(matrix[i][j]+matrix[i-1][j-1])%mod;
                    if (j==1) matrix[i][j]+=1;
                }
                else matrix[i][j]=matrix[i-1][j];
        int result=matrix[s.size()][t.size()];
        for (int i=0;i<s.size()+1;i++)
            delete [] matrix[i];
        return result%mod;
    }
};

119. 杨辉三角 II

简单题!!!

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> lb={{1}};
        for (int i=1;i<=rowIndex;i++)
        {
            vector<int> temp;
            temp.push_back(1);
            for (int j=1;j<i;j++)
                temp.push_back(lb[i-1][j-1]+lb[i-1][j]);
            temp.push_back(1);
            lb.push_back(temp);
        }
        return lb[rowIndex];
    }
};

198. 打家劫舍(LCR 089 打家劫舍)

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size()==1) return nums[0];
        if (nums.size()==2) return max(nums[0],nums[1]);
        int * lb=new int [nums.size()+1];
        lb[0]=0;lb[1]=nums[0];lb[2]=max(nums[0],nums[1]);
        for (int i=3;i<nums.size()+1;i++)
            lb[i]=max(lb[i-2],lb[i-3])+nums[i-1];
        int result=max(lb[nums.size()],lb[nums.size()-1]);
        delete [] lb;
        return result;
    }
};

213. 打家劫舍 II(LCR 090 打家劫舍 II)

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size()==1) return nums[0];
        if (nums.size()==2) return max(nums[0],nums[1]);
        int * lb=new int [nums.size()];
        lb[0]=0;lb[1]=nums[1];lb[2]=max(nums[1],nums[2]);
        for (int i=3;i<nums.size();i++)
            lb[i]=max(lb[i-2],lb[i-3])+nums[i];
        int result1=max(lb[nums.size()-2],lb[nums.size()-1]);
        lb[0]=0;lb[1]=nums[0];lb[2]=max(nums[0],nums[1]);
        for (int i=3;i<nums.size();i++)
            lb[i]=max(lb[i-2],lb[i-3])+nums[i-1];
        int result2=max(lb[nums.size()-2],lb[nums.size()-1]);
        delete [] lb;
        return max(result1,result2);
    }
};

就做到这里吧。文章来源地址https://www.toymoban.com/news/detail-825793.html

到了这里,关于算法专题:线性DP的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Peter算法小课堂—线性dp

    今天,你读完这篇文章,普及组的动态规划已经可以秒了。 求两个数列的最长公共子序列(Longest Common Subsequence,LCS)的长度。 数列 X 和 Y 的最长公共子序列 Z,是指 Z 既是 X 的子序列,又是 Y 的子序列,而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。 f[i][j]表示

    2024年04月23日
    浏览(37)
  • AcWing算法学习笔记:动态规划(背包 + 线性dp + 区间dp + 计数dp + 状态压缩dp + 树形dp + 记忆化搜索)

    算法 复杂度 时间复杂度0(nm) 空间复杂度0(nv) 代码 算法 通过滚动数组对01背包朴素版进行空间上的优化 f[i] 与 f[i - 1]轮流交替 若体积从小到大进行遍历,当更新f[i, j]时,f[i - 1, j - vi] 已经在更新f[i, j - vi]时被更新了 因此体积需要从大到小进行遍历,当更新f[i, j]时,f[i - 1,

    2024年02月21日
    浏览(43)
  • 算法基础复盘笔记Day10【动态规划】—— 线性DP

    ❤ 作者主页:欢迎来到我的技术博客😎 ❀ 个人介绍:大家好,本人热衷于 Java后端开发 ,欢迎来交流学习哦!( ̄▽ ̄)~* 🍊 如果文章对您有帮助,记得 关注 、 点赞 、 收藏 、 评论 ⭐️⭐️⭐️ 📣 您的支持将是我创作的动力,让我们一起加油进步吧!!!🎉🎉 1. 题目

    2023年04月21日
    浏览(82)
  • 《算法竞赛进阶指南》0x51 线性DP

    题意: N N N 个人站成左端对齐的 k k k 排,每排有 N i N_i N i ​ 人, N i N j N_i N_j N i ​ N j ​ 如果 i j i j i j ,则 N i N j N_i N_j N i ​ N j ​ 。每一排从左到右身高递减,每一列从后到前身高递减。询问方案数。 解析: 按照身高从大到小的顺序决定位置。在任意时刻,已经确定位

    2023年04月23日
    浏览(43)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(一)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月03日
    浏览(71)
  • 猿创征文 |【算法面试入门必刷】动态规划-线性dp(四)

    📦个人主页:一二三o-0-O的博客 🏆技术方向:C/C++客户端资深工程师(直播+音视频剪辑) 👨‍💻作者简介:数据结构算法与音视频领域创作者 📒 系列专栏:牛客网面试必刷 📣专栏目标:帮助伙伴们通过系统训练,掌握数据结构与算法,收获心仪Offer 📝推荐一个找工作

    2024年02月02日
    浏览(36)
  • 【算法专题--双指针算法】leetcode--283. 移动零、leetcode--1089. 复写零

    🍁你好,我是 RO-BERRY 📗 致力于C、C++、数据结构、TCP/IP、数据库等等一系列知识 🎄感谢你的陪伴与支持 ,故事既有了开头,就要画上一个完美的句号,让我们一起加油 双指针 常见的双指针有两种形式,一种是对撞指针,⼀种是左右指针。 对撞指针:一般用于顺序结构中

    2024年03月17日
    浏览(44)
  • 【LeetCode 算法专题突破】滑动窗口(⭐)

    学完了双指针算法,滑动窗口那肯定是逃不掉了,我个人感觉他俩就不分家,不把滑动窗口的题目好好刷上一刷我都难受 先来一道经典的滑动窗口试试水 题目链接:209. 长度最小的子数组 其实滑动窗口题目的解法都大同小异,我们基本上写几道题目,就能很好的掌握这个算

    2024年02月07日
    浏览(52)
  • 【LeetCode 热题 100】矩阵 专题(大多原地算法,需要一定思维)

    解题思路 在 代码注释中!

    2024年02月15日
    浏览(50)
  • LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)

    贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最后拿走最大数额的钱就是推出全局最优。 感觉像

    2024年02月09日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包