← 返回目录

算法笔试模拟题精解之“字符配对”

第 21 / 74 卷日期：

算法笔试模拟题精解之“字符配对”

贡献者 | 张鹏飞

简介：本题可以使用动态规划来解决，对于第 i 个字符，有选和不选两种，如果

选，则和第 i-1 个字符组合创造权值，如果不选，就单独出来没有权值，取两者中加

权最大的选择。

题目描述

题目等级：中等

知识点：DP

查看题目：字符配对

给你一个字符串，字符串中仅包含 "A","B", 现在有四种字符串 "AA","AB",

"BA","BB"，每种字符串都有他们的权值，问从给出的字符串中能够得到的最大权值

为多少 ( 一个字符只能属于一个子字符串 )？

输入一个字符串 s（1 <= |s| <=10^6）;

再输入一个数组，数组中包含四个数字 a,b,c,d，依次表示字符串 "AA","AB",

"BA","BB" 的权值 (1 <= a,b,c,d <= 100)。

输出权值的最大值。

示例 1

输入：

"ABA"

[1 ,2, 3, 4]

输出：

3

解题方法：DP

大致思路：动态规划问题，对于第 i 个字符，有选和不选两种，如果选，则和第

i-1 个字符组合创造权值，如果不选，就单独出来没有权值，取两者中加权最大的

选择。

具体过程：定义一个字典 map，key 分别为 "AA","AB","BA","BB"，value 为对

应的权值。定义大小为 n 的数组 dp，dp[i] 表示前 i 个字符组成的最大权值，毫无疑

问，dp[0]=0，dp[1]=map.get(s.substring(0, 2));

从 i=2 开始遍历字符串，对于 dp[i]，有两个选择，一种是让第 i 个字符独立，即

此时的权值 dp[i]=dp[i-1]，因为第 i 个字符没有创造价值。

另一种选择是让第 i 个字符有价值，即第 i-1 个字符和第 i 个字符组合创造价值，

此时 dp[i]=dp[i-2]+map.get(s.substring(i-1,i+1)). 针对这两个选择，取权值最大

的即可。

因此，dp[n-1] 为最终答案。

时间复杂度为 O(n)

空间复杂度为 O(n)

看完之后是不是有了想法了呢，题目直达链接：查看题目：字符配对

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”