คะแนนสูงสุดของคำที่สร้างจากตัวอักษรใน C++

ให้รายการคำ (words), รายการตัวอักษรเดี่ยว (letters) และคะแนนของแต่ละตัวอักษร ต้องหาคะแนนสูงสุดของชุดคำที่ถูกต้องที่สร้างจากตัวอักษรที่ให้

อาจไม่ใช้ตัวอักษรทั้งหมด และแต่ละตัวอักษรใช้ได้ครั้งเดียว คะแนน a-z กำหนดโดย score[0] ถึง score[25]

เช่น words = ["god","good","toc","cat"], letters = [a,g,o,o,d,d,d,c,t,t], 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] เอาต์พุต = 30 (good และ cat ให้คะแนนสูงสุด)

วิธีแก้ − ใช้ DP + Backtracking พร้อม Memoization ลองเลือก/ไม่เลือกแต่ละคำ

ตัวอย่าง

#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){ 
        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}