在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding

本文为大家介绍其中的第73题：字符配对 的题目解析，具体如下：

题目描述

题目等级：中等
知识点：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)

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