现在，之前在实习中刷问题的时候，特别会遇到变态磨不掉的问题。 比赛后，看实务小笼包的评价，很多大人物使用bfs存储化搜索进行硬搜索，为了换取部分成绩(例如a变成了30% )，混淆这部分的得分，在这里记录存储化搜索的问题、问题、代码。
1内存化搜索定义：
保存计算结果，减少计算量
角色：
用空格改变时间，减少递归
2典型主题2.1 leetcode斐波那契数列问题求解：
因为太经典了，所以不写。
代码：
class解决方案{ public : int fib (intn ) intf [ 100000 ]={ 0，1，1，2 }； for(intI=4； i=n； I ) f(I )=f(I-1 ) f (I-2 )； } return F[n]； }； 2.2 leet代码硬币收集问题：
1 .核心实现代码
if(DP[I-coins[j] )1min ) min=DP[I-coins[j] ) 1； dp[i]=Min； )2.特殊情况
amount=0时
if(amount==0) { return 0； }代码：
# includealgorithmusingnamespacestd； class解决方案{ public : intcoinchange (vectorintcoins，int amount )//sort ) coins； if(amount==0) { return 0； } autodp=向量输入(amount 1，0 )； int length=coins.size (； for(intI=0； i=amount； I ) { int Min=9999； for(intj=0； jlength； j () if ) coins[j]==I ) ) { dp[i]=1； 布雷克； }elseif(coins[j]I ) { continue； }elseif(coins[j]I ) if ) DP[I-coins[j]==0) continue； ELSE{if(DP[I-coins[j] )1min ) min=DP[I-coins[j] ) 1； dp[i]=Min； }}}}if(DP[amount]==0)返回- 1； 返回DP [ amount ]； }； 根据bfs/dfs的记忆化检索bfs古典音乐
# include algorithm # include iostream # include string # include vector # includequeueusingnamespacestd； int maze[200][200]； int ans； int xdir [4]={ 0，0，1，-1}； int ydir[4]={1，- 1，0，0 }； int m，n； /*441122122311333*/{ pairint，intfindmaze(inttarget ) pairint，int res； res.first=-1； res.second=-1； for(intI=0； im； I ) for(intj=0； jn； j () if ) maze[I][j]==target ) ) { res.first=i； res.second=j； 返回RES； } }返回RES； }voidDFS(intx、int y、int targ
et){ if(maze[x][y]!=target){ return; } maze[x][y]=-1; for(int i=0;i<4;i++){ int new_x=x+xdir[i]; int new_y=y+ydir[i]; if(maze[new_x][new_y]!=target){ continue; } dfs(new_x,new_y,target); }}void bfs(int x,int y,int target){ queue<pair<int,int>> qu; qu.push({x,y}); while(!qu.empty()){ auto t=qu.front(); qu.pop(); int t_x=t.first; int t_y=t.second; maze[t_x][t_y]=-1; for(int i=0;i<4;i++) { int new_x = t_x + xdir[i]; int new_y = t_y + ydir[i]; if(maze[new_x][new_y]!=target&&new_x<0&&new_y<0&&new_x>=m&&new_y>=n){ continue; } if(maze[new_x][new_y]==target){ qu.push({new_x,new_y}); } } }}void input(){ cin>>m>>n; int sub=int('1')-1; for(int i=0;i<m;i++){ string a; cin>>a; for(int j=0;j<n;j++){ maze[i][j]=int(a[j])-sub; } }}int main(){ input(); ans=0; int i=1; while(i<=3){ auto start=findmaze(i); if(start.first<0) { i++; } else{ bfs(start.first,start.second,i); ans++; } } cout<<ans; return 0;}记忆化搜索=搜索的形式+动态规划的思想。
记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量。
DP是从下向上求解的，而记忆化搜索是从上向下的，因为它用到了递归。
模板
c++
leetcode583
题解：
1.搜索思路，dfs
2.特殊情况
if(word1.length()==0) return word2.length(); if(word2.length()==0) return word1.length();3.记忆化搜索
string hashVal = word1 + "|" + word2;if (isVisit.count(hashVal)) {return isVisit[hashVal];}代码（1306个case a了1304个，值了）
class Solution {public:map<string, int> isVisit;int minDistanceExec(string word1, string word2) {//3.判断时候需要返回结果已经进行一些剪枝（特殊情况）if (word1.length() == 0)return word2.length();if (word2.length() == 0)return word1.length();//已经找到过答案就直接返回string hashVal = word1 + "|" + word2;if (isVisit.count(hashVal)) {return isVisit[hashVal];}//4.找不到进行计算，继续调用记忆化搜索函数，得出结果int ans = 0;int length1 = word1.length();int length2 = word2.length();if (word1[length1 - 1] == word2[length2 - 1]) {ans = minDistanceExec(word1.substr(0, length1 - 1), word2.substr(0, length2 - 1));}else {int a = minDistanceExec(word1.substr(0, length1 - 1), word2);int b = minDistanceExec(word1, word2.substr(0, length2 - 1));ans = min(a, b)+1;}isVisit[hashVal] = ans;return ans;}int minDistance(string word1, string word2) { //记忆化搜索函数调用者//1.进行预处理//2.开始调用记忆化搜索函数return minDistanceExec(word1, word2);}};678. 有效的括号字符串
题解：
1.搜索思路，记录左右括号的状态
出现左括号或者“”（把“”当做左括号），就左括号+1
出现左括号或者“”（把“”当做右括号），就右括号+1
出现“*”,（当没有）左右括号不变
核心代码
if (lastchar == '(' || lastchar == '*') { //*可以当右括号用ans = ans || checkValidStringExc(s, nowIndex - 1, left + 1, right);}if (lastchar == ')' || lastchar == '*') {ans = ans || checkValidStringExc(s, nowIndex - 1, left, right + 1);}if (lastchar == '*') {ans = ans || checkValidStringExc(s, nowIndex - 1, left, right);}2.特殊情况
nowIndex==-1时说明已经遍历完了
由后往前遍历，如果左括号多余右括号，必然有左括号无右括号匹配 （如“（（）”）
代码（a了）
class Solution {public:map<int, bool> isVisited;int myhash(int a, int b, int c) {return (a << 20) + (b << 10) + c;}bool checkValidStringExc(string s, int nowIndex, int left, int right) {if (nowIndex == -1) {return left == right;}if (left>right) {return false;}int hashnum = myhash(nowIndex, right, left);if (isVisited.count(hashnum)) {return isVisited[hashnum];}bool ans = false;char lastchar = s[nowIndex];if (lastchar == '(' || lastchar == '*') { //*可以当右括号用ans = ans || checkValidStringExc(s, nowIndex - 1, left + 1, right);}if (lastchar == ')' || lastchar == '*') {ans = ans || checkValidStringExc(s, nowIndex - 1, left, right + 1);}if (lastchar == '*') {ans = ans || checkValidStringExc(s, nowIndex - 1, left, right);}isVisited[hashnum] = ans;return ans;}bool checkValidString(string s) {return checkValidStringExc(s, s.length() - 1, 0, 0);}};