- 浏览: 21922 次
- 性别:
- 来自: 南京
最新评论
最大子序列
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2},它的和是8,达到最大;而 {5,-6,4,2}的最大子序列是{4,2},它的和是6。你已经看出来了,找最大子序列的方法很简单,只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。
代码如下:
#include<iostream>
using namespace std;
int MaxSubSeq(const int *arr,int len,int *start,int *end){
int max=0; //记录目前找到的最大子序列的和
int sum=0; //记录当前子序列的和
int begin=0,finish=0; //记录当前子序列的起始下标
*start=begin;*end=finish; //记录最长子序列的起始下标
for(int i=0;i<len;i++){
sum+=arr[i];
finish=i;
if(sum>max){
max=sum;
*end=finish;
*start=begin;
}
if(sum<=0){
sum=0;
begin=i+1;
}
}
return max;
}
int main(){
int arr[6]={5,-3,-2,12,9,-1};
int start,end;
int max=MaxSubSeq(arr,6,&start,&end);
cout<<"The MaxSubSeq is from position "<<start<<"to position "<<end<<"."<<endl;
cout<<"Sum of MaSubSeq: "<<max<<endl;
return 0;
}
最长公共子串(LCS)
找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下:
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//str1为横向,str2这纵向
const string LCS(const string& str1,const string& str2){
int xlen=str1.size(); //横向长度
vector<int> tmp(xlen); //保存矩阵的上一行
vector<int> arr(tmp); //当前行
int ylen=str2.size(); //纵向长度
int maxele=0; //矩阵元素中的最大值
int pos=0; //矩阵元素最大值出现在第几列
for(int i=0;i<ylen;i++){
string s=str2.substr(i,1);
arr.assign(xlen,0); //数组清0
for(int j=0;j<xlen;j++){
if(str1.compare(j,1,s)==0){
if(j==0)
arr[j]=1;
else
arr[j]=tmp[j-1]+1;
if(arr[j]>maxele){
maxele=arr[j];
pos=j;
}
}
}
// {
// vector<int>::iterator iter=arr.begin();
// while(iter!=arr.end())
// cout<<*iter++;
// cout<<endl;
// }
tmp.assign(arr.begin(),arr.end());
}
string res=str1.substr(pos-maxele+1,maxele);
return res;
}
int main(){
string str1("21232523311324");
string str2("312123223445");
string lcs=LCS(str1,str2);
cout<<lcs<<endl;
return 0;
}
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的,比如ADE和ABCDE的最长公共子序列是ADE。
我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程:
等号约定,C1是S1的最右侧字符,C2是S2的最右侧字符,S1‘是从S1中去除C1的部分,S2'是从S2中去除C2的部分。
LCS(S1,S2)等于下列3项的最大者:
(1)LCS(S1,S2’)
(2)LCS(S1’,S2)
(3)LCS(S1’,S2’)--如果C1不等于C2; LCS(S1',S2')+C1--如果C1等于C2;
边界终止条件:如果S1和S2都是空串,则结果也是空串。
下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应,矩阵中每个格子里的数字应该这么填,它等于以下3项的最大值:
(1)上面一个格子里的数字
(2)左边一个格子里的数字
(3)左上角那个格子里的数字(如果 C1不等于C2); 左上角那个格子里的数字+1( 如果C1等于C2)
举个例子:
G C T A
0 0 0 0 0
G 0 1 1 1 1
B 0 1 1 1 1
T 0 1 1 2 2
A 0 1 1 2 3
填写最后一个数字时,它应该是下面三个的最大者:
(1)上边的数字2
(2)左边的数字2
(3)左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格,以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大,那么任取其中之一,但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
下图给出了回溯法找出LCS的过程:
奉上代码:
01
#include<iostream>
02
#include<cstring>
03
#include<stack>
04
#include<utility>
05
#define LEFTUP 0
06
#define LEFT 1
07
#define UP 2
08
using namespace std;
09
int Max(int a,int b,int c,int *max){ //找最大者时a的优先级别最高,c的最低.最大值保存在*max中
10
int res=0; //res记录来自于哪个单元格
11
*max=a;
12
if(b>*max){
13
*max=b;
14
res=1;
15
}
16
if(c>*max){
17
*max=c;
18
res=2;
19
}
20
return res;
21
}
22
//调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。
23
string LCS(const string &str1,const string &str2){
24
int xlen=str1.size(); //横向长度
25
int ylen=str2.size(); //纵向长度
26
if(xlen==0||ylen==0) //str1和str2中只要有一个为空,则返回空
27
return "";
28
pair<int,int> arr[ylen+1][xlen+1]; //构造pair二维数组,first记录数据,second记录来源
29
for(int i=0;i<=xlen;i++) //首行清0
30
arr[0][i].first=0;
31
for(int j=0;j<=ylen;j++) //首列清0
32
arr[j][0].first=0;
33
for(int i=1;i<=ylen;i++){
34
char s=str2.at(i-1);
35
for(int j=1;j<=xlen;j++){
36
int leftup=arr[i-1][j-1].first;
37
int left=arr[i][j-1].first;
38
int up=arr[i-1][j].first;
39
if(str1.at(j-1)==s) //C1==C2
40
leftup++;
41
int max;
42
arr[i][j].second=Max(leftup,left,up,&arr[i][j].first);
43
// cout<<arr[i][j].first<<arr[i][j].second<<" ";
44
}
45
// cout<<endl;
46
} /*矩阵构造完毕*/
47
//回溯找出最长公共子序列
48
stack<int> st;
49
int i=ylen,j=xlen;
50
while(!(i==0&&j==0)){
51
if(arr[i][j].second==LEFTUP){
52
if(arr[i][j].first==arr[i-1][j-1].first+1)
53
st.push(i);
54
--i;
55
--j;
56
}
57
else if(arr[i][j].second==LEFT){
58
--j;
59
}
60
else if(arr[i][j].second==UP){
61
--i;
62
}
63
}
64
string res="";
65
while(!st.empty()){
66
int index=st.top()-1;
67
res.append(str2.substr(index,1));
68
st.pop();
69
}
70
return res;
71
}
72
int main(){
73
string str1="GCCCTAGCG";
74
string str2="GCGCAATG";
75
string lcs=LCS(str1,str2);
76
cout<<lcs<<endl;
77
return 0;
78
}
下面给一个Java版本
01
public static <E> List<E> longestCommonSubsequence(E[] s1,E[] s2){
02
int[][] num=new int[s1.length+1][s2.length+1];
03
for(int i=1;i<s1.length;i++){
04
for(int j=1;j<s2.length;j++){
05
if(s1[i-1].equals(s2[j-1])){
06
num[i][j]=1+num[i-1][j-1];
07
}
08
else{
09
num[i][j]=Math.max(num[i-1][j],num[i][j-1]);
10
}
11
}
12
}
13
System.out.println("lenght of LCS= "+num[s1.length][s2.length]);
14
int s1position=s1.length,s2position=s2.length;
15
List<E> result=new LinkedList<E>();
16
while(s1position!=0 && s2position!=0){
17
if(s1[s1position-1].equals(s2[s2position-1])){
18
result.add(s1[s1position-1]);
19
s1position--;
20
s2position--;
21
}
22
else if(num[s1position][s2position-1]>=num[s1position-1][s2position]){
23
s2position--;
24
}
25
else{
26
s1position--;
27
}
28
}
29
Collections.reverse(result);
30
return result;
31
}
std::endl是一个特殊值,称为操纵符(manipulator),将它写入输出流时具有输出换行的效果,并刷新与设备相关联的缓冲区(buffer)。通过刷新缓冲区用户可立即看到写入到流中的输出。
我在调试以上代码时在45行(cout<<endl;)处设置断点,结果发现“43行(cout<<arr[i][j].first<<arr[i][j].second<<" ";) 没有执行”,这就是因为43行末尾没有加endl,所以用户没有立即看到输出流中的数据。
最大子序列是要找出由数组成的一维数组中和最大的连续子序列。比如{5,-3,4,2}的最大子序列就是 {5,-3,4,2},它的和是8,达到最大;而 {5,-6,4,2}的最大子序列是{4,2},它的和是6。你已经看出来了,找最大子序列的方法很简单,只要前i项的和还没有小于0那么子序列就一直向后扩展,否则丢弃之前的子序列开始新的子序列,同时我们要记下各个子序列的和,最后找到和最大的子序列。
代码如下:
#include<iostream>
using namespace std;
int MaxSubSeq(const int *arr,int len,int *start,int *end){
int max=0; //记录目前找到的最大子序列的和
int sum=0; //记录当前子序列的和
int begin=0,finish=0; //记录当前子序列的起始下标
*start=begin;*end=finish; //记录最长子序列的起始下标
for(int i=0;i<len;i++){
sum+=arr[i];
finish=i;
if(sum>max){
max=sum;
*end=finish;
*start=begin;
}
if(sum<=0){
sum=0;
begin=i+1;
}
}
return max;
}
int main(){
int arr[6]={5,-3,-2,12,9,-1};
int start,end;
int max=MaxSubSeq(arr,6,&start,&end);
cout<<"The MaxSubSeq is from position "<<start<<"to position "<<end<<"."<<endl;
cout<<"Sum of MaSubSeq: "<<max<<endl;
return 0;
}
最长公共子串(LCS)
找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。其实这又是一个序贯决策问题,可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢?直接举个例子吧:"bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")
b a b
c 0 0 0
a 0 1 0
b 1 0 1
a 0 1 0
我们看矩阵的斜对角线最长的那个就能找出最长公共子串。
不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事,下面改进:当要在矩阵是填1时让它等于其左上角元素加1。
b a b
c 0 0 0
a 0 1 0
b 1 0 2
a 0 2 0
这样矩阵中的最大元素就是 最长公共子串的长度。
在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了,所以实际上在程序中可以用一维数组来代替这个矩阵。
代码如下:
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//str1为横向,str2这纵向
const string LCS(const string& str1,const string& str2){
int xlen=str1.size(); //横向长度
vector<int> tmp(xlen); //保存矩阵的上一行
vector<int> arr(tmp); //当前行
int ylen=str2.size(); //纵向长度
int maxele=0; //矩阵元素中的最大值
int pos=0; //矩阵元素最大值出现在第几列
for(int i=0;i<ylen;i++){
string s=str2.substr(i,1);
arr.assign(xlen,0); //数组清0
for(int j=0;j<xlen;j++){
if(str1.compare(j,1,s)==0){
if(j==0)
arr[j]=1;
else
arr[j]=tmp[j-1]+1;
if(arr[j]>maxele){
maxele=arr[j];
pos=j;
}
}
}
// {
// vector<int>::iterator iter=arr.begin();
// while(iter!=arr.end())
// cout<<*iter++;
// cout<<endl;
// }
tmp.assign(arr.begin(),arr.end());
}
string res=str1.substr(pos-maxele+1,maxele);
return res;
}
int main(){
string str1("21232523311324");
string str2("312123223445");
string lcs=LCS(str1,str2);
cout<<lcs<<endl;
return 0;
}
最长公共子序列
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的,比如ADE和ABCDE的最长公共子序列是ADE。
我们用动态规划的方法来思考这个问题如是求解。首先要找到状态转移方程:
等号约定,C1是S1的最右侧字符,C2是S2的最右侧字符,S1‘是从S1中去除C1的部分,S2'是从S2中去除C2的部分。
LCS(S1,S2)等于下列3项的最大者:
(1)LCS(S1,S2’)
(2)LCS(S1’,S2)
(3)LCS(S1’,S2’)--如果C1不等于C2; LCS(S1',S2')+C1--如果C1等于C2;
边界终止条件:如果S1和S2都是空串,则结果也是空串。
下面我们同样要构建一个矩阵来存储动态规划过程中子问题的解。这个矩阵中的每个数字代表了该行和该列之前的LCS的长度。与上面刚刚分析出的状态转移议程相对应,矩阵中每个格子里的数字应该这么填,它等于以下3项的最大值:
(1)上面一个格子里的数字
(2)左边一个格子里的数字
(3)左上角那个格子里的数字(如果 C1不等于C2); 左上角那个格子里的数字+1( 如果C1等于C2)
举个例子:
G C T A
0 0 0 0 0
G 0 1 1 1 1
B 0 1 1 1 1
T 0 1 1 2 2
A 0 1 1 2 3
填写最后一个数字时,它应该是下面三个的最大者:
(1)上边的数字2
(2)左边的数字2
(3)左上角的数字2+1=3,因为此时C1==C2
所以最终结果是3。
在填写过程中我们还是记录下当前单元格的数字来自于哪个单元格,以方便最后我们回溯找出最长公共子串。有时候左上、左、上三者中有多个同时达到最大,那么任取其中之一,但是在整个过程中你必须遵循固定的优先标准。在我的代码中优先级别是左上>左>上。
下图给出了回溯法找出LCS的过程:
奉上代码:
01
#include<iostream>
02
#include<cstring>
03
#include<stack>
04
#include<utility>
05
#define LEFTUP 0
06
#define LEFT 1
07
#define UP 2
08
using namespace std;
09
int Max(int a,int b,int c,int *max){ //找最大者时a的优先级别最高,c的最低.最大值保存在*max中
10
int res=0; //res记录来自于哪个单元格
11
*max=a;
12
if(b>*max){
13
*max=b;
14
res=1;
15
}
16
if(c>*max){
17
*max=c;
18
res=2;
19
}
20
return res;
21
}
22
//调用此函数时请注意把较长的字符串赋给str1,这主要是为了在回溯最长子序列时节省时间。如果没有把较长的字符串赋给str1不影响程序的正确执行。
23
string LCS(const string &str1,const string &str2){
24
int xlen=str1.size(); //横向长度
25
int ylen=str2.size(); //纵向长度
26
if(xlen==0||ylen==0) //str1和str2中只要有一个为空,则返回空
27
return "";
28
pair<int,int> arr[ylen+1][xlen+1]; //构造pair二维数组,first记录数据,second记录来源
29
for(int i=0;i<=xlen;i++) //首行清0
30
arr[0][i].first=0;
31
for(int j=0;j<=ylen;j++) //首列清0
32
arr[j][0].first=0;
33
for(int i=1;i<=ylen;i++){
34
char s=str2.at(i-1);
35
for(int j=1;j<=xlen;j++){
36
int leftup=arr[i-1][j-1].first;
37
int left=arr[i][j-1].first;
38
int up=arr[i-1][j].first;
39
if(str1.at(j-1)==s) //C1==C2
40
leftup++;
41
int max;
42
arr[i][j].second=Max(leftup,left,up,&arr[i][j].first);
43
// cout<<arr[i][j].first<<arr[i][j].second<<" ";
44
}
45
// cout<<endl;
46
} /*矩阵构造完毕*/
47
//回溯找出最长公共子序列
48
stack<int> st;
49
int i=ylen,j=xlen;
50
while(!(i==0&&j==0)){
51
if(arr[i][j].second==LEFTUP){
52
if(arr[i][j].first==arr[i-1][j-1].first+1)
53
st.push(i);
54
--i;
55
--j;
56
}
57
else if(arr[i][j].second==LEFT){
58
--j;
59
}
60
else if(arr[i][j].second==UP){
61
--i;
62
}
63
}
64
string res="";
65
while(!st.empty()){
66
int index=st.top()-1;
67
res.append(str2.substr(index,1));
68
st.pop();
69
}
70
return res;
71
}
72
int main(){
73
string str1="GCCCTAGCG";
74
string str2="GCGCAATG";
75
string lcs=LCS(str1,str2);
76
cout<<lcs<<endl;
77
return 0;
78
}
下面给一个Java版本
01
public static <E> List<E> longestCommonSubsequence(E[] s1,E[] s2){
02
int[][] num=new int[s1.length+1][s2.length+1];
03
for(int i=1;i<s1.length;i++){
04
for(int j=1;j<s2.length;j++){
05
if(s1[i-1].equals(s2[j-1])){
06
num[i][j]=1+num[i-1][j-1];
07
}
08
else{
09
num[i][j]=Math.max(num[i-1][j],num[i][j-1]);
10
}
11
}
12
}
13
System.out.println("lenght of LCS= "+num[s1.length][s2.length]);
14
int s1position=s1.length,s2position=s2.length;
15
List<E> result=new LinkedList<E>();
16
while(s1position!=0 && s2position!=0){
17
if(s1[s1position-1].equals(s2[s2position-1])){
18
result.add(s1[s1position-1]);
19
s1position--;
20
s2position--;
21
}
22
else if(num[s1position][s2position-1]>=num[s1position-1][s2position]){
23
s2position--;
24
}
25
else{
26
s1position--;
27
}
28
}
29
Collections.reverse(result);
30
return result;
31
}
std::endl是一个特殊值,称为操纵符(manipulator),将它写入输出流时具有输出换行的效果,并刷新与设备相关联的缓冲区(buffer)。通过刷新缓冲区用户可立即看到写入到流中的输出。
我在调试以上代码时在45行(cout<<endl;)处设置断点,结果发现“43行(cout<<arr[i][j].first<<arr[i][j].second<<" ";) 没有执行”,这就是因为43行末尾没有加endl,所以用户没有立即看到输出流中的数据。
发表评论
-
KMP快速字符串查找算法
2011-08-25 19:29 673在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
求解最大公约数问题
2011-08-25 19:27 700最大公因数,又称最大公约数。是指 [n(≧2)个自然数 a1, ... -
堆排序(Heap Sort)算法学习
2011-08-25 19:26 1087在程序设计相关领域, ... -
整数拆分问题的动态规划解法
2011-08-25 19:26 3074输入n,和k,问将n用1到k这k个数字进行拆分,有多少种拆分方 ... -
背包问题介绍与分析
2011-08-25 19:24 1034背包问题是在1978年由Merkel和Hellman提出的。它 ... -
求平方根sqrt()函数的底层算法效率问题
2011-08-25 19:23 1293我们平时经常会有一些数据运算的操作,需要调用sqrt,exp, ... -
面试中常见的一些算法问题
2011-08-25 19:22 700Problem 1 : Is it a loop ? ( ... -
各种排序算法的C++实现与性能比较
2011-08-25 19:21 927排序是计算机算法中非常重要的一项,而排序算法又有不少实现方法, ... -
背包问题之硬币找零问题
2011-08-25 19:19 1177设有6 种不同面值的硬 ... -
求能被1到20的数整除的最小正整数
2011-08-25 19:18 1374求能被1到20的数整除的最小正整数。最直觉的方法是求1到20这 ... -
买书折扣最优惠问题解法
2011-08-25 19:17 758题目:在节假日的时候 ... -
二叉树中的最近公共祖先问题
2011-08-25 19:16 1325题目:要求寻找二叉树中两个节点的最近的公共祖先,并将其返回。 ... -
判断一个整数是否是2的N次方
2011-08-25 19:04 1827题目:给定一个整数num,判断这个整数是否是2的N次方。比如, ... -
字符串逆序的算法汇总
2011-08-25 19:01 1061很早就准备写一个字符串系列的面试题,本来已经写好了,大概有十几 ... -
计算从1到N中1的出现次数
2011-08-25 18:59 602给定一个十进制整数N, ... -
KMP快速字符串查找算法
2011-08-25 18:57 967在C/C++语言编程过程中,一般的字符串搜索操作都是通过标准库 ... -
快速排序的递归实现
2011-08-25 18:54 761快速排序是对冒泡排序的一种改进。它的基本思想是:通过一次排序将 ... -
数字1亿里面有多少个1呢
2011-08-25 18:52 745乍看这题真够唬人的,群里看到这个题目后争先恐后的说看法。最简单 ... -
一道关于男女比例的面试题
2011-08-25 16:56 1043阿里巴巴的一道面试题:说澳大利亚的父母喜欢女孩,如果生出来的第 ...
相关推荐
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
最大子序列问题是一种经典的算法问题,它涉及到对一维数组中的连续子序列进行求和,目标是找到和最大的那个子序列。在这个问题中,我们通常使用动态规划的思想来解决。以下是对最大子序列求和算法的详细解释: 1. *...
**最长公共子串与最长公共子序列** 1. **最长公共子串**: 是指两个字符串中的最长的相同的子序列,需要连续。例如,字符串"ABABC"和"ABCBDAB"的最长公共子串是"ABC"。 2. **最长公共子序列**: 不要求连续,只...
在第五章中更是对动态规划常见的一些体型进行了总结整理,包括“最长公共子序列,最长公共子串,背包,最大子数组和”;最后summary总结整理了链表常见的问题包括“链表是否有环,链表环的入口,是否相交,排序等”...
在文档中提到了最长公共子串(LCS)和最长公共子序列(LCS)的计算。两者区别在于,子串要求字符连续,而子序列不要求。 - **最长公共子串**:给定两个字符串str1和str2,动态规划表dp[i][j]表示str1的前i个字符和...
最长公共子序列问题与最长公共子串类似,不同的是,子序列不要求连续,而子串要求连续。动态规划同样适用于这个问题的解决。 17. 最长递增子序列(LIS) 最长递增子序列问题是在一个数组中找到最长的严格递增的子...
4. 最长公共子序列:给定两个序列,求它们的最长公共子序列的长度。 5. 最长回文子串:要求找出字符串中的最长回文子串。 针对以上问题,动态规划可以使用“状态”和“状态转移方程”来描述问题的解决过程。状态是...
最长公共子序列 * 1035. 不相交的线 * 674. 最长连续子序列 * 718. 最长重复子数组 * 53. 最大子数组和 * 392. 判断子序列 * 115. 不同的子序列 这些题目考察了开发者和互联网从业者的能力,如何使用动态规划来...
2. 最长公共子序列(LCS):寻找两个字符串的最长子序列,子序列不必连续,但必须保持原有顺序。 3. 最短路径问题:例如Dijkstra算法或Floyd-Warshall算法的变种,寻找图中两点之间的最短路径。 4. 数学问题:如...
3. 最长公共子序列/子串:寻找两个序列中长度最长的相同子序列或子串,适用于文本比较和编辑距离计算。 4. 数字游戏:如nim游戏、石子游戏等,通过动态规划找到最优策略。 5. 递归问题的优化:如斐波那契数列、...
例如,背包问题、最长公共子序列和最短路径问题等。 5. **贪心算法**:贪心算法在每一步都采取局部最优解,期望得到全局最优解。比如Prim算法求最小生成树,Dijkstra算法求单源最短路径等。 6. **图论算法**:图论...
最大子序列和 Medium 判断能否跳到最后 Easy vector East 爬楼梯 Easy 单链表节点删除 Easy 合并数组 Medium 二叉树中序遍历 Easy 二叉树是否相等 Easy 二叉树最大深度 Easy 二叉树层序遍历 Easy 二叉树是否平衡 ...
4. **最大子数组和**: - 寻找一个数组中连续子数组的最大和,这可以使用Kadane's algorithm解决。 5. **字符串排列**: - 给定一个字符串,找到所有可能的排列组合,这需要用到回溯算法。 6. **最小覆盖子串**...
最大子序列和 58 最后一个单词的长度 63 不同路径 II 66 加一 67 二进制求和 69 x的平方 70 爬楼梯 83 删除排序链表中的重复元素 108 将有序数组转换为二叉搜索树 112 路径总和 125 验证回文串 136 只出现一次的数字...
- 背包问题、最长公共子序列、斐波那契数列:这些都是动态规划的经典案例,通过构建状态转移方程来解决复杂问题。 5. **回溯法**: - 八皇后问题、数独求解:回溯法常用于约束满足问题,通过尝试和撤销来寻找解决...
4. **动态规划**:动态规划是一种解决最优化问题的常用方法,适用于有重叠子问题和最优子结构的问题,如背包问题、最长公共子序列、斐波那契数列等。 5. **贪心算法**:在每一步选择局部最优解,期望达到全局最优。...
2. **LeetCode053: 最大子数组和** - 这是一个经典的动态规划问题,我们通过维护当前最大子数组和以及全局最大子数组和来解决。 3. **LeetCode062: 不同路径** - 这个问题中,我们使用动态规划来计算从左上角到达右...
笔记中的动态规划部分,labuladong详细介绍了状态转移方程和备忘录等概念,并通过斐波那契数列、最长公共子序列等经典问题,讲解了动态规划的思想和解题步骤。掌握了这些方法之后,读者能解决诸如背包问题、编辑距离...
- **动态规划**:定义一个二维数组dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最长公共子串的长度。 - **状态转移方程**:如果s1[i-1] == s2[j-1],则dp[i][j] = dp[i-1][j-1] + 1;否则dp[i][j] = 0。 -...
- **最长公共单调子序列的定义:** 在两个序列中找到最长的、同时为单调递增(或递减)的子序列。 - **求解方法:** 如动态规划。 **13.10 最长子序列** - **最长子序列的定义:** 在一个序列中找到最长的子序列。...