遇到一个字符配对的问题，求解答。
给你一个字符串，字符串中仅包含"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)。输出权值的最大值。
写回答
-
定义一个字典 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] 为最终答案。 输入："ABA" [1,2, 3,4] 输出：3
2021-12-23 18:32:58赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
