【动态规划数学】2745. 构造最长的新字符串|1607

本文涉及知识点

C++动态规划数学

LeetCode2745. 构造最长的新字符串

给你三个整数 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

动态规划

AA的后面，一定不能是AB或AB，一定能是BB。
BB的后面一定能是AA或AB，一定不能是BB。
AB后面可以是AA或AB，一定不能是BB。
第二种情况和第三种情况可以合并，都是不能以B开头。

动态规划的状态表示

dp[x][y][z][0或1]：的最大长度。前三维是AA BB AB的数量，第四维表示字符的结尾是不时A。空间复杂度：O(xyz)。

动态规划的转移方程

枚举前置状态，如果结尾是A。可以连BB。否则能连AA或AB。

动态规划的初始值

dp[x-1][y][z][1] =dp[x][y-1][z][0] = dp[x][y][z-1]=2，其它全为-1000。

动态规划的填表顺序

枚举前置状态，x,y,z从大到小。

动态规划的返回值

dp的最大值

数学

两个AA无法连在一起，中间无法插入AB，只能插入BB。性质一:如果x >y+1，则 x-y-1的个AA一定无法使用。
性质二：如果y > x+1，则y-x-1的BB无法使用。
性质三：所有的AB都可以用上，先将AB连在一起。如果x 和y都大于0，则插到两者之间；如果全为AA，则插在最前面；如果全为BB，则追加到最后。
答案是：2*(min(x,y+1)+min(y,x+1)+z)。

代码

核心代码

class Solution {
public:int longestString(int x, int y, int z) {return 2*(min(x,y+1)+min(y,x+1)+z);}
};

单元测试

int x,y,z;TEST_METHOD(TestMethod11){x = 2, y = 5, z = 1;auto res = Solution().longestString(x, y, z);AssertEx(12, res);}TEST_METHOD(TestMethod12){x = 3, y = 2, z = 2;auto res = Solution().longestString(x, y, z);AssertEx(14, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功