動(dòng)態(tài)規(guī)劃 滑動(dòng)窗口【力扣雙周賽 107】

為什么我的記憶化總是出問題
class Solution {
? ? unordered_map<string, int> mp;
? ? int dfs(vector<string>& words, int cur, char start, char end){
? ? ? ? int res =0;
? ? ? ?
? ? ? ? if(cur == words.size()){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? else{
? ? ? ? ? ? string curstring ;
? ? ? ? ? ? curstring += (char)cur;
? ? ? ? ? ? // curstring +=' ';
? ? ? ? ? ? curstring+= start;
? ? ? ? ? ? curstring += end;
? ? ? ? ? ? cout<< curstring<< endl;
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ? if(mp.count(curstring)){
? ? ? ? ? ? ? ? return mp[curstring] ;
? ? ? ? ? ? }
? ? ? ? ? ? string & s= words[cur];
? ? ? ? ? ? int len = s.size();
? ? ? ? ? ? char c = s.back();
? ? ? ? ? ? // 接到總串后面
? ? ? ? ? ? int r1 = dfs(words, cur+1, start, c ) ?+ len- (end == s[0] ? 1: 0);
? ? ? ? ? ?
? ? ? ? ? ? // 接到總串前
? ? ? ? ? ? int r2 = dfs(words, cur+1, s[0], end ) ?+ len - (c == start ? 1: 0);
? ? ? ? ? ? res = min(r1, r2);
? ? ? ? ? ? mp[curstring] = res;
? ? ? ? }
? ? ? ? return res;
? ? }
public:
? ? int minimizeConcatenatedLength(vector<string>& words) {
? ? ? ? int len1= words[0].size();
? ? ? ? // cout<< s<<endl;
? ? ? ? return dfs(words, 1, words[0][0], words[0].back() ) + len1;
? ? }
};