算法专题：记忆化搜索-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法专题：记忆化搜索。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

参考练习习题总集

前置知识

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

练习习题

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;
    }
};