Giả sử chúng ta có một danh sách các từ, một danh sách các chữ cái đơn lẻ và điểm cho mỗi ký tự. Chúng ta phải tìm điểm tối đa của bất kỳ tập hợp từ hợp lệ nào được hình thành bằng cách sử dụng các chữ cái cho trước.
Chúng ta có thể không sử dụng tất cả các ký tự trong letters và mỗi chữ cái chỉ có thể được sử dụng một lần. Điểm của các chữ cái 'a', 'b', 'c', ..., 'z' được cho bởi score[0], score[1], ..., score[25] tương ứng.
Vì vậy, nếu đầu vào giống như words = ["god", "good", "toc", "cat"], letters = [a,g,o,o,d,d,d,c,t,t] và 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], thì đầu ra sẽ là 30, ở đây good và cat tạo ra điểm tối đa.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa mảng 2D dp
Định nghĩa hàm calc(), nhận s, một map m, mảng sc,
ans := 0
for khởi tạo i := 0, khi i < kích thước của s, cập nhật (tăng i lên 1), thực hiện −
x := s[i]
nếu m[x] <= 0, thì −
trả về 0
(giảm m[x] xuống 1)
ans := ans + sc[x - 'a']
trả về ans
Định nghĩa hàm solve(), nhận i, status, mảng các cặp v, một map m, mảng s,
nếu i bằng -1, thì −
trả về 0
x := giá trị .second của v[i]
ans := 0
nếu status bằng 1, thì −
ans := calc(x, m, s)
nếu ans > 0 và status bằng 1, thì −
for khởi tạo j := 0, khi j < kích thước của x, cập nhật (tăng j lên 1), thực hiện −
(giảm m[x[j]] xuống 1)
trả về ans + max của solve(i - 1, 0, v, m, s) và solve(i - 1, 1, v, m, s)
Từ phương thức main, thực hiện như sau −
ans := 0
Định nghĩa một map m
for khởi tạo i := 0, khi i < kích thước của l, cập nhật (tăng i lên 1), thực hiện −
(tăng m[l[i]] lên 1)
Định nghĩa mảng v các cặp
for khởi tạo i := 0, khi i < kích thước của w, cập nhật (tăng i lên 1), thực hiện −
x := w[i]
flag := calc(x, m, s)
nếu flag khác 0, thì −
chèn { flag, x } vào cuối v
sắp xếp mảng v
dp := Định nghĩa mảng 2D kích thước (kích thước của v) x 2 và điền -1
trả về max của solve(kích thước của v, 0, v, m, s) và solve(kích thước của v, 1, v, m, s)
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#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)); } Đầu vào
{"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} Đầu ra
30