題目描述
X星球的考古學家發(fā)現(xiàn)了一批古代留下來的密碼。
這些密碼是由A、B、C、D 四種植物的種子串成的序列。
仔細分析發(fā)現(xiàn)，這些密碼串當初應該是前后對稱的（也就是我們說的鏡像串）。
由于年代久遠，其中許多種子脫落了，因而可能會失去鏡像的特征。

你的任務是：
給定一個現(xiàn)在看到的密碼串，計算一下從當初的狀態(tài)，它要至少脫落多少個種子，才可能會變成現(xiàn)在的樣子
輸入
輸入一行，表示現(xiàn)在看到的密碼串（長度不大于1000）
輸出
要求輸出一個正整數(shù)，表示至少脫落了多少個種子。
樣例輸入
ABCBA
樣例輸出
0
樣例輸入
ABDCDCBABC
樣例輸出
3
dotcpp平臺真的是缺斤少兩，不僅錯誤數(shù)據(jù)多而且連樣例數(shù)據(jù)還不給完整了。。第二個樣例是應有的。
思路：從兩頭開始遍歷，遇見不一樣的字符，這個時候我們就要考慮是從左邊取比較好還是右邊取比較好了，這就需要比較了。在dfs的時候，會重復遇見很多情況，因此需要記憶化一下。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e3+100; int dp[maxx][maxx]; string s; int n;inline int dfs(int l,int r) {if(l==r) return dp[l][r]=0;if(l>r) return 0;if(dp[l][r]!=-1) return dp[l][r];int ans=0;int i=l,j=r;while(s[i]==s[j]&&i<=j) i++,j--;if(i<j) ans=min(dfs(i+1,j),dfs(i,j-1))+1;return dp[l][r]=ans; } int main() {cin>>s;n=s.length();memset(dp,-1,sizeof(dp));int ans=dfs(0,n-1);printf("%d\n",ans);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][2016年第七届真题]密码脱落（记忆化搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。