在eclipse中做网站开发,上海企业网站制作,唐山网站建设系统,360个人网站建设目录 最⻓回⽂⼦序列#xff08;动态规划-区间dp#xff09;
题目解析
讲解算法原理
编写代码
添加字符#xff08;字符串#xff09;
题目解析
讲解算法原理
编写代码 最⻓回⽂⼦序列#xff08;动态规划-区间dp#xff09;
题目解析
1.题目链接#xff1a;最…目录 最⻓回⽂⼦序列动态规划-区间dp
题目解析
讲解算法原理
编写代码
添加字符字符串
题目解析
讲解算法原理
编写代码 最⻓回⽂⼦序列动态规划-区间dp
题目解析
1.题目链接最长回文子序列_牛客题霸_牛客网
2.题目描述 描述 给定一个字符串找到其中最长的回文子序列并返回该序列的长度。 注回文序列是指这个序列无论从左读还是从右读都是一样的。 本题中子序列字符串任意位置删除klen(s)k0个字符后留下的子串。 数据范围字符串长度满足 1 \le n \le 10001≤n≤1000 进阶空间复杂度 O(n^2)O(n2) 时间复杂度 O(n^2)O(n2) 输入描述 输入一个字符串 输出描述 输出最长回文子序列 示例1 输入 abccsb 输出 4 说明 分别选取第2、3、4、6位上的字符组成“bccb”子序列是最优解 示例2 输入 abcdewa 输出 3 说明 分别选取第一个和最后一个a再取中间任意一个字符就是最优解 讲解算法原理
解法 算法思路 基础的区间dp问题 1. 状态表⽰ dp[i][j] 表⽰字符串 [i, j] 范围内的最⻓回⽂⼦序列的⻓度2. 状态转移⽅程 ◦ 当 i j 的时候只有⼀个字符⻓度为1 ◦ 当 i j 的时候分情况讨论 ▪ s[i] s[j]dp[i][j] dp[i 1][j - 1];▪ s[i] ! s[j]dp[i][j] max(dp[i 1][j], dp[i][j - 1]) 3. 返回值 dp[0][n - 1] 。
编写代码
c算法代码
#include iostream
#include string
using namespace std;
int dp[1010][1010];
int main()
{string s;cin s;int n s.size();for(int i n - 1; i 0; i--){dp[i][i] 1; for(int j i 1; j n; j) { if(s[i] s[j]) dp[i][j] dp[i 1][j - 1] 2; else dp[i][j] max(dp[i 1][j], dp[i][j - 1]); }}cout dp[0][n - 1] endl;return 0;
}
java算法代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in new Scanner(System.in); char[] s in.next().toCharArray(); int n s.length; int[][] dp new int[n][n];for(int i n - 1; i 0; i--){dp[i][i] 1; for(int j i 1; j n; 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]); }}System.out.println(dp[0][n - 1]);}
}
添加字符字符串
题目解析
1.题目链接添加字符_牛客笔试题_牛客网
2.题目描述 牛牛手里有一个字符串A羊羊的手里有一个字符串BB的长度大于等于A所以牛牛想把A串变得和B串一样长这样羊羊就愿意和牛牛一起玩了。 而且A的长度增加到和B串一样长的时候对应的每一位相等的越多羊羊就越喜欢。比如abc和abd对应相等的位数为2为前两位。 牛牛可以在A的开头或者结尾添加任意字符使得长度和B一样。现在问牛牛对A串添加完字符之后不相等的位数最少有多少位 输入描述: 第一行为字符串A第二行为字符串BA的场地小于等于B的长度B的长度小于等于50.字符均为小写字母。输出描述: 输出一个整数表示A串添加完字符之后不相等的位数最少有多少位 示例1 输入 abe cabc 输出 1 讲解算法原理
解法 算法思路 枚举所有字符串a与字符串b相对应的位置。
编写代码
c算法代码
#include iostream
#include string
using namespace std;
string a, b;
int main()
{cin a b;int m a.size(), n b.size(); int ret m;for(int i 0; i n - m; i) // 枚举 b 的起始位置 {int tmp 0; for(int j 0; j m; j) { if(a[j] ! b[i j]) { tmp; }}ret min(tmp, ret);}cout ret endl;return 0;
}java算法代码
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in new Scanner(System.in); char[] a in.next().toCharArray(); char[] b in.next().toCharArray(); int m a.length, n b.length; int ret m;for(int i 0; i n - m; i) // 枚举 b 的起始位置 {int tmp 0; for(int j 0; j m; j) { if(a[j] ! b[i j]) { tmp; }}ret Math.min(ret, tmp);}System.out.println(ret);}
}
