假设我们有一个单词列表，一个字母列表和每个字符的分数。我们必须找到使用给定字母组成的任何有效单词集的最大分数。
我们可能不会在字母中使用所有字符，并且每个字母只能使用一次。字母“ 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的大小）x 2，并用-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