算法训练营day52_动态规划（3.17提前写）
创始人
2025-05-29 23:27:04
0次
算法训练营day52_动态规划（3.17提前写）
子序列问题也是个经典问题，之前比较熟，先开这个专题；
300.最长递增子序列
- f(i)表示以i结尾的最长子序列长度；
- 转移：遍历i之前的j作为倒数第二个元素，如果i的值>j的值，那么可以转移过来；
- 初始化：所有f最开始都包括自己，初始为1；
- 遍历:外层i，内层j；
class Solution {
public:int lengthOfLIS(vector& nums) {int len=nums.size();vector f(len,1);for(int i=0;i 674.最长连续递增序列
与上题不同点在于连续，i只能从i-1迭代过来；
class Solution {
public:int findLengthOfLCIS(vector& nums) {int n=nums.size();vector f(n,1);for(int i=1;inums[i-1]) f[i]=f[i-1]+1;}int ans=0;for(int i=0;i 718.最长重复子数组
首先，子数组是连续的！子序列是不连续的；
最长公共子数组，转移只有一个情况；
class Solution {
public:int findLength(vector& nums1, vector& nums2) {int n1=nums1.size(),n2=nums2.size();vector> f(n1+1,vector(n2+1,0));for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){if(nums1[i-1]==nums2[j-1]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);}}int ans=0;for(int i=1;i<=n1;i++){for(int j=1;j<=n2;j++){ans=max(ans,f[i][j]);}}return ans;}
};
相关内容
热门资讯
上海特大案件曝光！涉案金额超亿...
今年以来，公安部会同金融监管总局开展打击金融领域黑灰产违法犯罪专项工作，对保险等领域违法犯罪进行重点...
关于单方面免签政策常见问题，国...
今天（11月23日），国家移民管理局针对单方面免签政策常见问题进行解答。 1.哪些国家人员可适用单方...
“最快护士”张水华再夺冠
新京报记者 刘锦涵
制作 葛佳丹 ▲新京报我们视频出品（ID：wevideo） 11月23日，“最...
原创 沉...
在国际关系的复杂舞台上，每一个动作都可能引发连锁反应。近期，高市早苗的发言无疑是这一舞台上的一次重要...
宁夏回族自治区党委书记，用“玫...
“特别是何杰勇夺马拉松男子冠军，充分证明宁夏也能生长出绚丽的玫瑰……” 11月22日，宁夏回族自治区...
原创 日...
小泉进次郎的表态，无疑是对高市早苗政策的公开反击。尽管两人曾是同一阵营的人物，并且高市将小泉任命为防...
法律明白人｜白广万：学法律强本...
“以前村民来问遗产分割、合同纠纷的问题，我心里一点底都没有，只能劝大家别着急，给不出实在的办法。”回...
科技周报|多品牌手机遭遇“绿线...
多品牌手机遭遇“绿线门”，售后政策引不满 近期一场由手机屏幕绿线问题引发的消费维权潮在社交平台上持续...
美政府再次对加州提起诉讼
参考消息网11月23日报道据美联社11月21日报道，特朗普政府起诉加利福尼亚州向非法留美学生提供州内...
传“警银通”郑州暂时停用，有银...
10天前，#律师银行取4万元遭盘问报警#登上热搜。关于“银行反诈层层加码”的讨论一直在继续。 11月...