【动态规划】【字符串】1092. 最短公共超序列

时间:2024-02-11 23:41:52 标签:  最短  

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

LeetCode1092最短公共超序列

给你两个字符串 str1 和 str2,返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个,则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符(也可能不删除),可以得到字符串 s ,那么 s 就是 t 的一个子序列。
示例 1:
输入:str1 = “abac”, str2 = “cab”
输出:“cabac”
解释:
str1 = “abac” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 的第一个 "c"得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。
示例 2:
输入:str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出:“aaaaaaaa”
提示:
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。

动态规划

原理

超串一定以str1.back或str2.back结尾 。

动态规划的状态表示

dp[i][j][use]=x,表示str1[0,i)和str2[0,j)的最短超串长度。use的含义如下:
{ 此超串的末尾已经匹配了 s t r 1 , s t r 2 3 此超串末尾匹配了 s t r 1 1 此超串末尾匹配了 s t r 2 2 \begin{cases} 此超串的末尾已经匹配了str1,str2 & 3 \\ 此超串末尾匹配了str1 & 1 \\ 此超串末尾匹配了str2 & 2 \end{cases} 此超串的末尾已经匹配了str1,str2此超串末尾匹配了str1此超串末尾匹配了str2312

动态规划的转移方程

dp[i][j][use] 更新dp[i+1][j][use1] preCh = (1&use) ? str1[i-1] : str2[j-1]。const int use1 = bNew ? 1 : (1 | use);
{ d p [ i + 1 ] [ j ] [ u s e 1 ] = m i n ( , d p [ i ] [ j ] [ u s e ] + 1 ) ( p r e C h ! = s t r 1 [ i ] ) 或 ( 1 位与 u s e ) d p [ i + 1 ] [ j ] [ u s e 1 ] = m i n ( , d p [ i ] [ j ] [ u s e ] ) e l s e \begin{cases} dp[i+1][j][use1] = min(,dp[i][j][use]+1) & (preCh!=str1[i])或(1位与use) \\ dp[i+1][j][use1] = min(,dp[i][j][use]) & else \\ \end{cases} {dp[i+1][j][use1]=min(,dp[i][j][use]+1)dp[i+1][j][use1]=min(,dp[i][j][use])(preCh!=str1[i])(1位与use)else
更新dp[i][j+1] [use1]类似

动态规划的填表顺序

I+j之和从1到大处理,use 从1到3,这样可以保证动态规划的无后效性。

动态规划的初始值

dp[1][0][1] =1;
dp[0][1][2] = 1;
其它dp 的值INT_MAX/2

动态规划的返回值

根据dp2 逆序组装。

代码

核心代码

class Solution {
public:string shortestCommonSupersequence(string str1, string str2) {m_r = str1.length();m_c = str2.length();vector<vector<vector<int>>> dp(m_r + 1, vector<vector<int>>(m_c + 1,vector<int>(4, INT_MAX / 2)));dp[1][0][1] =1;		dp[0][1][2] = 1;for (int len = 1; len < m_r + m_c; len++){for (int len1 = max(0,len-m_c); len1 <= min(len, m_r); len1++){const int len2 = len - len1;for (int use = 1; use <= 3; use++){const int preLen = dp[len1][len2][use];if (preLen >= INT_MAX / 2){continue;}const char preCh = (1 & use) ? str1[len1 - 1] : str2[len2 - 1];if (len1 < m_r){bool bNew = (preCh != str1[len1]) || (1 & use );const int use1 = bNew ? 1 : (1 | use);const int iNewLen = preLen + bNew;dp[len1 + 1][len2][use1] = min(dp[len1 + 1][len2][use1], iNewLen);		}if (len2 < m_c){bool bNew = (preCh != str2[len2]) || (2 & use );const int use1 = bNew ? 2 : (2 | use);const int iNewLen = preLen + bNew;dp[len1 ][len2 + 1][use1] = min(dp[len1][len2 + 1][use1], iNewLen);}}				}}string strRet;for (int len1 = m_r, len2 = m_c; len1 + len2 > 0; ){int use = std::min_element(dp[len1][len2].begin(), dp[len1][len2].end()) - dp[len1][len2].begin();const char preCh = (1 & use) ? str1[len1 - 1] : str2[len2 - 1];strRet += preCh;if (1 & use ){len1--;}if (2 & use ){len2--;}}std::reverse(strRet.begin(), strRet.end());return strRet;}int m_r, m_c;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}}int main()
{	string str1,str2;{Solution sln;str1 = "abac", str2 = "cab";auto res = sln.shortestCommonSupersequence(str1, str2);assert(-1 != res.find(str1));assert(-2 != res.find(str1));Assert((int)res.length(),5 );}{Solution sln;str1 = "aaaaaaaa", str2 = "aaaaaaaa";auto res = sln.shortestCommonSupersequence(str1, str2);assert(-1 != res.find(str1));assert(-2 != res.find(str1));Assert(res.length(), string("aaaaaaaa").length());}
}

2023年1月版

先求最长公共子序列。
如果str1[i]==str2[j], 则一个字符匹配两个串。
否则比较dp[i-1][j] 和dp[i][j-1],采用公共子序列大的。

class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
vector<vector> dp;
{
dp.assign(str1.length() + 1, vector(str2.length() + 1));
for (int i = 1; i <= str1.length(); i++)
{
for (int j = 1; j <= str2.length(); j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i-1] == str2[j-1])
{
dp[i][j] = max(dp[i][j],dp[i - 1][j - 1] + 1);
}
}
}
}
string str;
int i = str1.length();
int j = str2.length();
str1 = " " + str1;
str2 = " " + str2;
while (i > 0 || j > 0)
{
if (0 == i)
{
str += str2[j–];
}
else if (0 == j)
{
str += str1[i–];
}
else if (str1[i] == str2[j])
{
str += str1[i];
i–, j–;
}
else
{
if (dp[i - 1][j] == dp[i][j])
{
str += str1[i–];
}
else
{
str += str2[j–];
}
}
}
return std::string(str.rbegin(), str.rend());
}
};

2023年8月版

class Solution {
public:
string shortestCommonSupersequence(string str1, string str2) {
m_c1 = str1.length();
m_c2 = str2.length();
vector<vector> dp(m_c1, vector(m_c2));
vector < vector<pair<int, int>>> vPre(m_c1, vector<pair<int, int>>(m_c2,std::make_pair<>(-1,-1)));
dp[0][0] = str1[0] == str2[0];
if (0 == dp[0][0])
{
vPre[0][0] = std::make_pair(0, -1);
}
for (int j = 1; j < m_c2; j++)
{
if (str1[0] == str2[j])
{
dp[0][j] = 1;
vPre[0][j] = std::make_pair(-1, j - 1);
}
else
{
dp[0][j] = dp[0][j - 1];
vPre[0][j] = std::make_pair(0, j - 1);
}
}
for (int i = 1; i < m_c1; i++)
{
if (str1[i] == str2[0])
{
dp[i][0] = 1;
vPre[i][0] = std::make_pair(i - 1, -1);
}
else
{
dp[i][0] = dp[i-1][0];
vPre[i][0] = std::make_pair(i-1,0);
}
}
for (int i = 1; i < m_c1; i++)
{
for (int j = 1; j < m_c2; j++)
{
if (str1[i] == str2[j])
{
dp[i][j] = 1 + dp[i - 1][j - 1];
vPre[i][j] = std::make_pair(i - 1, j - 1);
continue;
}
if (dp[i - 1][j] > dp[i][j - 1])
{
dp[i][j] = dp[i - 1][j];
vPre[i][j] = std::make_pair(i - 1, j);
}
else
{
dp[i][j] = dp[i ][j - 1];
vPre[i][j] = std::make_pair(i , j - 1);
}
}
}
int iNum = dp.back().back();
vector vRet;
auto it = std::make_pair(m_c1-1,m_c2-1);
for ( 😭-1 != it.first) && (-1 != it.second)😉
{
auto pre = vPre[it.first][it.second];
if (it.first != pre.first)
{
vRet.emplace_back(str1[it.first]);
}
else
{
vRet.emplace_back(str2[it.second]);
}
it = pre;
}
for (int i = it.first; i >= 0; i–)
{
vRet.emplace_back(str1[i]);
}
for (int i = it.second; i >= 0; i–)
{
vRet.emplace_back(str2[i]);
}
std::reverse(vRet.begin(), vRet.end());
vRet.emplace_back(0);
return vRet.data();
}
int m_c1, m_c2;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

来源:分享自作者个人站点/博客

智能推荐

作者推荐 【动态规划】【前缀和】【C&#43;&#43;算法】LCP 57. 打地鼠 本文涉及知识点 动态规划汇总 LeetCode1092最短公共超序列 给你两个字符串 str1 和 st

标签:最短  

作者推荐 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径 本文涉及知识点 动态规划汇总 状态压缩 字符串 LeetCode943 最短超级串 给定一个字符

标签:最短  

Problem: 1143. 最长公共子序列 文章目录 题目描述思路解题方法复杂度Code

标签:序列  

作者推荐 视频算法专题 涉及知识点 动态规划 字符串 LeetCode87扰乱字符串 使用下面描述的算法可以扰乱字符串

标签:字符串  

参考博客&#xff1a;https://leetcode.cn/problems/interleaving-string/solutions/48146/dong-tai-gui-hua-zhu-xing-jie-shi-python3-by-zhu-3

标签:字符串  

作者推荐 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径 本文涉及知识点 动态规划汇总 LeetCode940. 不同的子序列 II 给定一个字符串 s&#xff0c

标签:字符串  

给定两个长度分别为 N 和 M 的字符串 A 和 B &#xff0c;求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。 输入格式 第一行包含两个整数 N 和

标签:线性  

2707. 字符串中的额外字符 题目描述 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将

标签:字符串  

2707. 字符串中的额外字符 题目描述 给你一个下标从 0 开始的字符串 s 和一个

标签:字符串  

作者推荐 【动态规划】【前缀和】【C&#43;&#43;算法】LCP 57. 打地鼠 本文涉及知识点 动态规划汇总 LeetCode1278分割回文串 III 给你一个由小写字母组成的字符串

标签:回文  

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 字符串 LeetCode140:单词拆分 II 给定一个字符串 s 和一个字符串字典 wordDict &#xff

标签:字符串  

对于问题&#xff0c;两个字符串的最长公共子序列长度进行求解&#xff0c;首先要知道子序列的定义&#xff0c;如果说给定一个字符串&#xff0c;对这个字符串中的原有字符进行不改变字符相对位置的删除&#xff0c;这里的相对位置就是处于前还是后的相对关系&#xff0c;进行删除字符的操作之后&#xff0c;所形成的新的字符串就是原来的字符串的子序列。 这里要求解的问题&#xff0c;就是给定两个字符串S1和S2&#xff0c;对这两个字符串进行子序列的比对&#xff0c;得到一个共同的子序列&#xff0c;求这个子序列的最长字符长度。如下例子&#xff1a;

标签:字符串  

392.判断子序列&#xff1a; 初始思路&#xff1a;                  左为判断公共子序列&#xff0c;右为判断子序列&#xff0c;感觉代码完

标签:序列  

作者推荐 【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数 本文涉及知识点 动态规划汇总 LeetCode1397. 找到所有好字符串 给你两个长度为 n 的字符串 s1

标签:字符串  

动态规划求解子序列问题 1.子序列&#xff08;不连续&#xff09;1.1最长上升子序列1.2最长公共子序列1.3不相交的线 2.子序列

标签:之子  

给定一个长度为 N 的数列&#xff0c;求数值严格单调递增的子序列的长度最长是多少。 输入格式 第一行包含整数 N 。 第二行包含 N 个整数&#xff0c;表示完整序列。 输出格式

标签:线性  

作者推荐 【动态规划】【字符串】【行程码】1531. 压缩字符串 本文涉及知识点 动态规划汇总 C&#43;&#43;算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频

标签:字符串  

目录 1143.最长公共子序列

标签:第二天  

作者推荐 【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数 本文涉及知识点 动态规划汇总 记忆化搜索 回文 字符串 LeetCode1312. 让字符串成为回文串的最少插入次数

标签:回文  

题目描述 设有由n(1≤n≤200)个整数组成的数列&#xff0c;记为:b(1)、b(2)、……、b(n)&#xff0c;若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求&#xff0c;当原数列出之后&#xff0c;求出最长的不下降序列。 例如13&#xff0c;7&#xff0c;9&#xff0c;16&#xff0c;38&#xff0c;24&#xff0c;37&#xff0c;18&#xff0c;44&#xff0c;19&#xff0c;21&#xff0c;22&#xff0c;63&#xff0c;15。 例中13&

标签:序列  

解题思路 求两个数组或者字符串的最长公共子序列问题&#xff0c;肯定是要用动态规划的。下面的题解并不难&#xff0c;你肯定能看懂。 首先&#xff0c;区分两个概念&#xff1a;子序列可以是不连续的&#xff1b;子数组&#xff08;子字符串&#xff09;需要是连续的&#xff1b; 另外&#xff0c;动态规划也是有套路的&#xff1a;单个数组或者字符串要用

标签:序列  

一.SDS定义 free 属性值为0&#xff0c;标识SDS没有分配任何未使用空间。len  属性值为5&#xff0c;标识SDS保存了一个5字节长度的字符串。buf  属性是一个char类型数组&#xff0c;数组的前5个字节保存了&#xff0c;&#39;R&#39; &#39;e&#39; &#39;d&#39; &#39;i&#39; &#39;s&#39; 五

标签:字符串  

问题描述 最长公共子序列(Longest Common Subsequence&#xff0c;LCS)即求两个序列最长的公共子序列(可以不连续)。比如3 2 1 4 5和1 2 3 4 5两个序列&#xff0c;最长公共子序列为2 4 5 长度为3。解决这个问题

标签:序列  

最长公共子序列和最长公共子串区别最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别:子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续。例如&nbsp;&nbsp;X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么,{a, 1, 1}是X和Y的最长公共子序列,但不是它们的最长公共字串。最优子结

标签:序列  最长  

猜你喜欢

2.1 SDS的定义struct { //buf中已使用的字节数,等于SDS所保存字符串的长度 int len; //buf中未使用的字节长度 int free; //字节数组,用于保存字符串 char[] buf;}2.2 SDS与C字符串的区别C字符串SDS获取字符串长度的复杂度为 O(N)获取字符串长度的复杂度为O(1)

标签:字符串  区别  简单  动态  Redis  

动态规划 动态规划就像是解决问题的一种策略&#xff0c;它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题&#xff0c;并将每个小问题的解保存起来。这样&#xff0c;当我们需要解决原始问题的时候&#xff0c;我们就可以直接利用已经计算好的小问题的解&#xff0c;而不需要重复计算。 动态规划与数学归纳法思想上十分相似。 数学归纳法&#xff1a; 基础步骤&#xff08;base case&#xff09;&#xff1a;首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况&#xff0c;可以直接验证命题是否成立。

标签:回文  

一、概述1.设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段,通过组合子问题而解决整个问题的解。2.基本要素(1)最优子结构最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解

标签:动态  

动态规划(Dongtai Planning&nbsp;Dynamic Programming,简称DP)&nbsp; &nbsp; &nbsp;多阶段决策过程的最优化问题在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。当然,各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线,这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题就称为多

标签:动态  

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 LeetCode115 不同的子序列 给你两个字符串 s 和 t &#xff0c;统计并返回在 s 的 子序列 中

标签:序列  

动态规划 思路&#xff1a; 假设 dp[i][j] 是 text1[0:i] 和 text2[0:j] 最长公共子序列的长度&#xff1b;则 dp[0][j] &#61; 0&#xff0c;&#xff08;空字符串和任何字符串的最长公共子序列的长度都是 0&#xff09;&#xff1b;同理 dp[i][j] &#61; 0&#xff1b;状态转移方程&#xff1a; 当 text1[i - 1] &#61; text2[j - 1] 时&#xff0c;dp[i][j] &#61; dp[i - 1][j - 1] &#43; 1&#xff1b;否

标签:序列  

Floyd算法的精髓在于动态规划的思想,即每次找最优解时都建立在上一次最优解的基础上,当算法执行完毕时一定是最优解对于邻接矩阵w,w保存最初始情况下任意两点间的直接最短距离,但没有加入中继点进行考虑如w[1][2]=20,即表示点1与点2的当前最短距离(直接距离)为20对于路径矩阵path,保存了点i到点j的最短路径中下一个点的位置,如path[1][2]=0,表示1->2的路径中的下一个点为结点0Floyd算法对所有中继点在任意两点中进行循环遍历.即k从0-n时考虑(i->k,k->j)的路径是否小于(i->j)的路,如果小于即更新邻接矩阵w的值与path矩阵中的值,使其始终保持最短

标签:最短  路径  两点  动态  Floyd  

动态规划&#xff08;Dynamic Programming, DP&#xff09;是解决复杂问题的一个强大工具&#xff0c;它将问题分解成更小的子问题&#xff0c;并使用这些子问题的解决方案来构建整体问题的解决方案。在深入探讨最短编辑距离问题之前&#xff0c;让我们先理解什么是动态规划&#xff0c;以及如何通过动态规划的视角来看待这个问题。 原题链接&#xff1a;72. 编辑距离 - 力扣&#xff08;Le

标签:距离  

2024-1-11 文章目录 [2645. 构造有效字符串的最少插入数](https://leetcode.cn/problems/minimum-additions-to-make-valid-st

标签:字符串  

目录概述SDS(动态字符串)SDS(动态字符串)与c语言字符串的区别1、概述String类型底层实现的简单动态字符串sds,是可以修改的字符串。它采用预分配冗余空间的方式来减少内存的频繁分配。2、SDS动态字符串

标签:字符串  章节  动态  Redis  

目录 今日知识点&#xff1a; 01背包的路径输出 计算位和的数位dp 不用管字符串&#xff0c;只需要看好约束dp转移的变量

标签:字符串  

文章目录 &#xff08;一&#xff09;序列1 序列1.1 序列结构2.2 序列访问方式2.3 序列遍历2.4 序列运算符

标签:字符串  

题目描述 观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径&#xff0c;使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。   在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。 输入 第一个行包含R(1≤ R≤1000)&#xff0c

标签:金字塔  

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 动态规划 LeetCode44 通配符匹配 给你一个输入字符串 (s) 和一个字符模式 § &#xff0c;请你实现一个支持

标签:通配符  

Python-求解两个字符串的最长公共子序列 一、问题描述 给定两个字符串&#xff0c;求解这两个字符串的最长公共子序列&#xff08;Longest Common Sequence&#xff09;。比如字符串1&#xff1a;BDCABA&#xff1b;字符串2&#xff1a;ABCBD

标签:序列  

作者推荐 视频算法专题 简介 动态规划&#xff08;Dynamic Programming&#xff0c;DP&#xff09;是运筹学的一个分支&#xff0c;是求解决策过程最优化的过程。每次决策依赖于当前状态&#xff0c

标签:动态  

一、爬楼梯 题目一&#xff1a;57. 爬楼梯 57. 爬楼梯&#xff08;第八期模拟笔试&#xff09; 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  每次你可以爬至多m (1 <&#61; m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f;  注意&#xff1a;给定 n 是一个正整数。 输入描述 输入共一行&#xff0c;包含两个正整数&#xff0c;分别表示n, m 输出描述 输出一个整数&#xff0c;表示爬到楼顶的方法数。

标签:动态  

题目链接&#xff1a;等差数列划分 目录 题目解析&#xff1a; 算法原理 1.状态表示

标签:等差数列  

Every day a Leetcode 题目来源&#xff1a;2207. 字符串中最多数目的子字符串 解法1&#xff1a;贪心 &#43; 一次遍历 设 pattern 的第一个字符为 x&#xff0c;第

标签:字符串  

首先&#xff0c;必须先明白&#xff0c;这个点并不难&#xff0c;我给大家梳理一遍就会明白。 反序列化字符串逃逸就是序列化过程中逃逸出来字符&#xff0c;是不是很简单&#xff0c;哈哈哈&#xff01; 好了&#xff0c;不闹了&#xff0c;其实&#xff1a; 这里你们只要懂得一个基础&#xff1a; serialize() 函数序列化后可以保留其原始数据类型和结构&#xff0c; 而filte

标签:字符串  

Problem: LCR 165. 解密数字 文章目录 题目描述:思路解题方法复杂度Code

标签:数字  

1017. 怪盗基德的滑翔翼怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已,怪盗基德只能操作受损的滑翔翼逃脱。假设城市中一共有N幢建筑排成一条线,每幢建筑的高度各不相同。初始时,怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑,但是不能中途改变方向(因

标签:序列  算法  最长  模型  动态  

题目链接&#xff1a;最长湍流子数组 目录 题目解析&#xff1a; 算法原理 1.状态表示

标签:数组  

作者推荐 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径 本文涉及知识点 动态规划汇总 LeetCode879. 盈利计划 集团里有 n 名员工&#xff0c;他们可

标签:计划  

摘要:大部分动态规划能解决的问题,都可以通过回溯算法来解决,只不过回溯算法解决起来效率比较低,时间复杂度是指数级的。动态规划算法,在执行效率方面,要高很多。本文分享自华为云社区《深入浅出动态规划算法》,作者:嵌入式视觉。一,动态规划概念动态规划比较适合用来求解最优问题,比如求最大值、最小值等等。它可以非常显著地降低时间复杂度,提高代码的执行效率。它和递归

标签:不太  算法  常规  思维  动态  

相关问题

相关文章

热门文章

推荐文章

相关标签