题目:
给你三个整数 x ,y 和 z 。
这三个整数表示你有 x 个 “AA” 字符串,y 个 “BB” 字符串,和 z 个 “AB” 字符串。你需要选择这些字符串中的部分字符串(可以全部选择也可以一个都不选择),将它们按顺序连接得到一个新的字符串。新字符串不能包含子字符串 “AAA” 或者 “BBB” 。
请你返回新字符串的最大可能长度。
子字符串 是一个字符串中一段连续 非空 的字符序列。
示例 1:
输入:x = 2, y = 5, z = 1
输出:12
解释: 我们可以按顺序连接 “BB” ,“AA” ,“BB” ,“AA” ,“BB” 和 “AB” ,得到新字符串 “BBAABBAABBAB” 。
字符串长度为 12 ,无法得到一个更长的符合题目要求的字符串。
示例 2:
输入:x = 3, y = 2, z = 2
输出:14
解释:我们可以按顺序连接 “AB” ,“AB” ,“AA” ,“BB” ,“AA” ,“BB” 和 “AA” ,得到新字符串 “ABABAABBAABBAA” 。
字符串长度为 14 ,无法得到一个更长的符合题目要求的字符串。
提示:
1 <= x, y, z <= 50文章来源:https://www.toymoban.com/news/detail-521202.html
思路:
动态规划文章来源地址https://www.toymoban.com/news/detail-521202.html
java代码:
class Solution {
int[][][][] memo;
public int longestString(int x, int y, int z) {
this.memo = new int[x + 1][y + 1][z + 1][3];
for (int i = 0; i <= x; ++i) {
for (int j = 0; j <= y; ++j) {
for (int k = 0; k <= z; ++k) {
Arrays.fill(memo[i][j][k], -1);
}
}
}
return Math.max(dfs(x, y, z, 0), dfs(x, y, z, 1));
}
public int dfs(int x, int y, int z, int k) {
if (memo[x][y][z][k] != -1) {
return memo[x][y][z][k];
}
int res = 0;
if (k == 0) {
if (y > 0) {
res = dfs(x, y - 1, z, 1) + 2;
}
} else {
if (x > 0) {
res = dfs(x - 1, y, z, 0) + 2;
}
if (z > 0) {
res = Math.max(res, dfs(x, y, z - 1, 2) + 2);
}
}
memo[x][y][z][k] = res;
return res;
}
}
到了这里,关于【算法题】2745. 构造最长的新字符串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!