C ++中字母构成的最大分数词
假设我们有一个单词列表，一个字母列表和每个字符的分数。我们必须找到使用给定字母组成的任何有效单词集的最大分数。
我们可能不会在字母中使用所有字符，并且每个字母只能使用一次。字母“a”，“b”，“c”，...，“z”的得分分别由得分[0]，得分[1]，...，得分[25]给出。
因此，如果输入像单词=[“god”，“good”，“toc”，“cat”]，字母=[a，g，o，o，d，d，d，c，t，t]和分数=[5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0，0,0,0]，则输出将为30，此处good和cat得分最高。
为了解决这个问题，我们将遵循以下步骤-
定义一个2D数组dp
定义一个函数calc()，它将使用s，一个映射m，一个数组sc，
回答：=0
对于初始化i：=0，当i<s的大小时，更新（将i增加1），执行-
返回0
x：=s[i]
如果m[x]<=0，则-
（将m[x]减1）
ans：=ans+sc[x-'a']
返回ans
定义一个函数solve()，它将接受i，状态，成对的v数组，一个映射m，一个数组s，
如果i与-1相同，则-
返回0
x：=.v[i]的第二个值
回答：=0
如果状态与1相同，则-
ans：=calc(x,m,s)
如果ans>0并且状态等于1，则-
（将m[x[j]]减1）
对于初始化j：=0，当j<x的大小时，更新（将j增加1），执行-
返回ans+求解(i-1,0,v,m,s)和求解(i-1,1,v,m,s)的最大值
从主要方法中，执行以下操作-
回答：=0
定义一张映射
对于初始化i：=0，当i<l的大小时，更新（将i增加1），执行-
（将m[l[i]]增加1）
定义成对的数组v
对于初始化i：=0，当i<w的大小时，更新（将i增加1），执行-
在v的末尾插入{flag，x}
x：=w[i]
标志：=calc(x,m,s)
如果flag不为零，则-
对数组v排序
dp：=定义一个2D数组，大小为（v的大小）x2，并用-1填充
返回最大的solve（v，0，v，m，s的大小）和solve（v，1，v，m，s的大小）
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int> > dp;
int calc(string s, map<char, int> m, vector<int>& sc){
int ans = 0;
for (int i = 0; i < s.size(); i++) {
char x = s[i];
if (m[x] <= 0)
return 0;
m[x]--;
ans += sc[x - 'a'];
}
return ans;
}
int solve(int i, int status, vector<pair<int, string> > v,
map<char, int> m, vector<int>& s){
if (i == -1)
return 0;
string x = v[i].second;
int ans = 0;
if (status == 1)
ans = calc(x, m, s);
if (ans > 0 && status == 1) {
for (int j = 0; j < x.size(); j++) {
m[x[j]]--;
}
}
return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
}
int maxScoreWords(vector<string>& w, vector<char>& l,
vector<int>& s){
int ans = 0;
map<char, int> m;
for (int i = 0; i < l.size(); i++)
m[l[i]]++;
vector<pair<int, string> > v;
for (int i = 0; i < w.size(); i++) {
string x = w[i];
int flag = calc(x, m, s);
if (flag) {
v.push_back({ flag, x });
}
}
sort(v.begin(), v.end());
dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
1, 1, v, m, s));
}
};
main(){
Solution ob;
vector<string> words = {"god", "good", "toc", "cat"};
vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
cout << (ob.maxScoreWords(words, letters, score));
}输入项
{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0}输出结果
30