算法专题：记忆搜索

参考练习习题总集

前置知识

没有什么特别知识，只有一些做题经验。要做这类型的题目，首先写出暴力搜索，然后写出记忆搜索，大概就是这个流程。感觉说了一些废话。

练习习题

87. 扰乱字符串

TLE：(自己写的难蚌代码)

class Solution {
public:unordered_set<string> jh;bool isScramble(string s1, string s2) {func(s1,0,s1.size()-1);return jh.find(s2)!=jh.end();}void func(string s,int l,int r){if (l==r) {jh.insert(s);return;}for (int i=l;i<r;i++){func(s,l,i);func(s,i+1,r);string temp=s.substr(0,l)+s.substr(i+1,r-i)+s.substr(l,i-l+1)+s.substr(r+1,s.size()-1-r);func(temp,l,l+r-i-1);func(temp,r-i+l,r);}}
};

TLE：(一个较合适的思路)

class Solution {
public:bool isScramble(string s1, string s2) {if (s1==s2) return true;if (check(s1,s2)) return false;for (int i=1;i<s1.size();i++){string a=s1.substr(0,i),b=s1.substr(i);string c=s2.substr(0,i),d=s2.substr(i);if (isScramble(a,c) and isScramble(b,d)) return true;string e=s2.substr(0,s1.size()-i),f=s2.substr(s1.size()-i);if (isScramble(a,f) and isScramble(b,e)) return true;}return false;}bool check(const string & s1,const string & s2){int lb[26] {};for (int i=0;i<s1.size();i++)lb[s1[i]-'a']+=1;for (int i=0;i<s2.size();i++)lb[s2[i]-'a']-=1;for (int i=0;i<26;i++)if (lb[i]!=0) return true;return false;}
};

AC：(刚上手就放弃的屑)
temp[i][j][k]：从s1[i]开始k个字符，从s2[j]开始k个字符，是否互为扰乱串呢。(包括下标本身字符)。if (temp[i][j][len]!=0) return temp[i][j][len]==1;是关键这句删除就是上面那种解法。

class Solution {
public:vector<vector<vector<int>>> temp;string string1,string2;int n;bool isScramble(string s1,string s2) {if (s1.size()!=s2.size()) return false;string1=s1;string2=s2;n=s1.size();temp.resize(n,vector<vector<int>> (n,vector<int> (n+1,0)));return dfs(0,0,n);}bool dfs(int i,int j,int len){if (temp[i][j][len]!=0) return temp[i][j][len]==1;string a=string1.substr(i,len),b=string2.substr(j,len);if (a==b){temp[i][j][len]=1;return true;}if (check(a,b)){temp[i][j][len]=-1;return false;}for (int k=1;k<len;k++) {if (dfs(i,j,k) and dfs(i+k,j+k,len-k)){temp[i][j][len]=1;return true;}if (dfs(i,j+len-k,k) and dfs(i+k,j,len-k)){temp[i][j][len]=1;return true;}}temp[i][j][len]=-1;return false;}bool check(const string & s1,const string & s2){int lb[26] {};for (int i=0;i<s1.size();i++)lb[s1[i]-'a']+=1;for (int i=0;i<s2.size();i++)lb[s2[i]-'a']-=1;for (int i=0;i<26;i++)if (lb[i]!=0) return true;return false;}
};

97. 交错字符串

MLE：(第一反应还是暴搜)

class Solution {
public:string string1,string2;unordered_set<string> jh;bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;string1=s1;string2=s2;string string3;func(0,0,string3);return jh.find(s3)!=jh.end();}void func(int l1,int l2,string s){if (l1<string1.size())func(l1+1,l2,s+string1[l1]);if (l2<string2.size())func(l1,l2+1,s+string2[l2]);if (l1==string1.size() and l2==string2.size())jh.insert(s);}
};

TLE：(优化一下，怎么还是没有过啊，我要疯了)

class Solution {
public:string string1,string2,string3;unordered_set<string> jh;bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;string1=s1;string2=s2;string3=s3;string string4;func(0,0,string4);return jh.find(s3)!=jh.end();}void func(int l1,int l2,string s){if (l1<string1.size() and string1[l1]==string3[s.size()])func(l1+1,l2,s+string1[l1]);if (l2<string2.size() and string2[l2]==string3[s.size()])func(l1,l2+1,s+string2[l2]);if (l1==string1.size() and l2==string2.size())jh.insert(s);}
};

TLE：(继续优化，真是过不了一点啊，最后一点真是可恶，受不了了)

class Solution {
public:string string1,string2,string3;bool flag=false;bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;string1=s1;string2=s2;string3=s3;func(0,0);return flag;}void func(int l1,int l2){if (!flag){if (l1<string1.size() and string1[l1]==string3[l1+l2])func(l1+1,l2);if (l2<string2.size() and string2[l2]==string3[l1+l2])func(l1,l2+1);if (l1==string1.size() and l2==string2.size())flag=true;}}
};

AC：(嗨嗨嗨导这么久了终于给我导出来了)
temp[i][j]：从s1[i]开始剩余字符，从s2[j]开始剩余字符，能否组成剩余部分。(包括下标本身字符)

class Solution {
public:string string1,string2,string3;vector<vector<int>> temp;bool isInterleave(string s1, string s2, string s3) {if (s1.size()+s2.size()!=s3.size()) return false;string1=s1;string2=s2;string3=s3;temp.resize(s1.size()+1,vector<int> (s2.size()+1,0));return func(0,0);}bool func(int l1,int l2){if (l1==string1.size() and l2==string2.size()) return true;if (temp[l1][l2]!=0) return temp[l1][l2]==1;bool result=false;if (l1<string1.size() and string1[l1]==string3[l1+l2])result|=func(l1+1,l2);if (l2<string2.size() and string2[l2]==string3[l1+l2])result|=func(l1,l2+1);temp[l1][l2]=result?1:-1;return result;}
};

375. 猜数字大小II

AC：(题都没有读懂的屑）
temp[l][r]：区间(l,r)的最小花费。

class Solution {
public:vector<vector<int>> temp;int getMoneyAmount(int n) {temp.resize(n+5,vector<int> (n+5,0));return dfs(1,n);}int dfs(int l,int r){if (l>=r) return 0;if (temp[l][r]!=0) return temp[l][r];int result=INT_MAX;for (int i=l;i<=r;i++){int result_temp=max(dfs(l,i-1),dfs(i+1,r))+i;result=min(result,result_temp);}temp[l][r]=result;return result;}
};

403. 青蛙过河

AC：(不看题解也能做啦)
cache[now][next]：从第0个石头开始，走now石头到next石头，是否能够到达终点。

class Solution {
public:vector<int> lb;vector<vector<int>> cache;bool canCross(vector<int>& stones) {if (stones[1]!=1) return false;lb=stones;cache.resize(stones.size(),vector<int> (stones.size(),0));return dfs(0,1);}bool dfs(int now,int next){if (next==lb.size()-1) return true;if (cache[now][next]!=0) return cache[now][next]==1;vector<int> temp;int steps=lb[next]-lb[now];for (int i=next+1;i<lb.size();i++){if (lb[i]==lb[next]+steps-1) temp.push_back(i);if (lb[i]==lb[next]+steps) temp.push_back(i);if (lb[i]==lb[next]+steps+1) temp.push_back(i);if (lb[i]>=lb[next]+steps+2) break;}for (int i=0;i<temp.size();i++)if (dfs(next,temp[i])){cache[next][temp[i]]=1;return true;}else cache[next][temp[i]]=-1;return false;}
};

464. 我能赢吗

超标超标还是超标。
这里共有三个关键：
首先就是思路问题，我有一个错的思路：不论我去选择什么，最终结果我都能赢。这种想法不正确的(例如：输入样例4、6。只要先手去选择1，后手无论怎么选择，先手全部情况能赢。但是按照错误思路，先手如果去选择4，那么先手必然会输。)。也就是说选手只会选择成功最佳方案。
WA：

class Solution {
public:int num1,num2;unordered_set<int> jh;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal) return false;num1=maxChoosableInteger;num2=desiredTotal;for (int i=1;i<=maxChoosableInteger;i++) jh.insert(i);return dfs(0,0);}bool dfs(int times,int scores){int iter=0,length=jh.size();int * lb=new int [length];for (auto zz=jh.begin();zz!=jh.end();zz++){lb[iter]=*zz;iter+=1;}for (int i=0;i<length;i++){if (scores+lb[i]>=num2){if (times%2==0) continue;delete [] lb;return false;}jh.erase(lb[i]);if (!dfs(times+1,scores+lb[i])) {delete [] lb;return false;}jh.insert(lb[i]);}delete [] lb;return true;}
};

所以正确思路应是：我的对手十分强大，我选择数必须保证，对手必须全部输掉，否则那么不选这数，继续进行下次循环，循环结束如没找到，那么我就不能够赢。
TLE：

class Solution {
public:int num1,num2;unordered_set<int> jh;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal) return false;num1=maxChoosableInteger;num2=desiredTotal;for (int i=1;i<=maxChoosableInteger;i++) jh.insert(i);return dfs(0,0);}bool dfs(int times,int scores){int iter=0,length=jh.size();int * lb=new int [length];for (auto zz=jh.begin();zz!=jh.end();zz++){lb[iter]=*zz;iter+=1;}for (int i=0;i<length;i++){jh.erase(lb[i]);if (scores+lb[i]>=num2) {jh.insert(lb[i]);delete [] lb;return true;}if (!dfs(times+1,scores+lb[i])) {jh.insert(lb[i]);delete [] lb;return true;}jh.insert(lb[i]);}delete [] lb;return false;}
};

暴力我们写出来了，我们该写记忆搜索。但是我们发现由于使用集合并不好写，所以第二关键就是，必须换种存储方式。
TLE：

class Solution {
public:int num1,num2,x=1;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal) return false;num1=maxChoosableInteger;num2=desiredTotal;x=(x<<maxChoosableInteger)-1;return dfs(0,0);}bool dfs(int times,int scores){for (int i=1;i<=num1;i++){if (((1<<(i-1))&x)==0) continue;x-=(1<<(i-1));if (scores+i>=num2) {x+=(1<<(i-1));return true;}if (!dfs(times+1,scores+i)) {x+=(1<<(i-1));return true;}x+=(1<<(i-1));}return false;}
};

第三关键记忆搜索
AC：

class Solution {
public:int num1,num2,x=1;vector<int> lb;bool canIWin(int maxChoosableInteger, int desiredTotal) {if ((1+maxChoosableInteger)*maxChoosableInteger/2<desiredTotal) return false;num1=maxChoosableInteger;num2=desiredTotal;x=(x<<maxChoosableInteger)-1;lb.resize(1<<maxChoosableInteger,0);return dfs(0,0);}bool dfs(int times,int scores){if (lb[x]!=0) return lb[x]==1;for (int i=1;i<=num1;i++){if (((1<<(i-1))&x)==0) continue;x-=(1<<(i-1));if (scores+i>=num2) {x+=(1<<(i-1));lb[x]=1;return true;}if (!dfs(times+1,scores+i)) {x+=(1<<(i-1));lb[x]=1;return true;}x+=(1<<(i-1));}lb[x]=-1;return false;}
};

494. 目标和

直接暴力
AC：

class Solution {
public:int num,result=0;vector<int> lb;int findTargetSumWays(vector<int>& nums, int target) {num=target;lb=nums;dfs(0,0);return result;}void dfs(int begin,int count){if (begin==lb.size()){if (count==num) result+=1;return;}dfs(begin+1,count+lb[begin]);dfs(begin+1,count-lb[begin]);}
};

552. 学生出勤记录II

首先暴力
TLE：

class Solution {
public:int mod=1e9+7;int checkRecord(int n) {return dfs(n,0,0)%mod;}int dfs(int n,int A,int P){if (n==0) return 1;int count=0;if (A==0) count=(count+dfs(n-1,1,0))%mod;if (P<=1) count=(count+dfs(n-1,A,P+1))%mod;count=(count+dfs(n-1,A,0))%mod;return count;}
};

记忆搜索
AC：

class Solution {
public:vector<vector<vector<int>>> lb;int mod=1e9+7;int checkRecord(int n) {lb.resize(n,vector<vector<int>> (2,vector<int> (3,0)));return dfs(n,0,0)%mod;}int dfs(int n,int A,int P){if (n==0) return 1;if (lb[n-1][A][P]!=0) return lb[n-1][A][P];int count=0;if (A==0) count=(count+dfs(n-1,1,0))%mod;if (P<=1) count=(count+dfs(n-1,A,P+1))%mod;count=(count+dfs(n-1,A,0))%mod;lb[n-1][A][P]=count;return count;}
};

576. 出借的路径数

首先暴力
TLE：

class Solution {
public:int length,width,mod=1e9+7;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {length=m,width=n;int count=0;for (int i=1;i<=maxMove;i++)count=(count+dfs(i,startRow,startColumn))%mod;return count;}int dfs(int times,int x,int y){if (times==0){if (x==-1 or x==length or y==-1 or y==width) return 1;return 0;}if (x==-1 or x==length or y==-1 or y==width) return 0;int count=0;if (x>=0) count=(count+dfs(times-1,x-1,y))%mod;if (x<length) count=(count+dfs(times-1,x+1,y))%mod;if (y>=0) count=(count+dfs(times-1,x,y-1))%mod;if (y<width) count=(count+dfs(times-1,x,y+1))%mod;return count;}
};

记忆搜索
wc超时了，怎么办，怎么办，哎呦，你干嘛啊
TLE：

class Solution {
public:int length,width;vector<vector<vector<int>>> lb;int mod=1e9+7;int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {length=m,width=n;lb.resize(maxMove,vector<vector<int>> (m,vector<int> (n,0)));int count=0;for (int i=1;i<=maxMove;i++)count=(count+dfs(i,startRow,startColumn))%mod;return count;}int dfs(int times,int x,int y){if (times==0){if (x==-1 or x==length or y==-1 or y==width) return 1;return 0;}if (x==-1 or x==length or y==-1 or y==width) return 0;if (lb[times-1][x][y]!=0) return lb[times-1][x][y];int count=0;if (x>=0) count=(count+dfs(times-1,x-1,y))%mod;if (x<length) count=(count+dfs(times-1,x+1,y))%mod;if (y>=0) count=(count+dfs(times-1,x,y-1))%mod;if (y<width) count=(count+dfs(times-1,x,y+1))%mod;lb[times-1][x][y]=count;return count;}
};

我寻思这时间复杂度也不高也就$50^3$。
破大防了，C(传)T(统)M(美)D(德)。