1樓：
來講乙個歪門邪道。
首先觀察函式名：lps。
讓我們猜測一下 lps 是什麼的縮寫吧。
因為接觸過 LIS、LCS 等典型演算法，所以猜測 l 代表longest。
暫時不知道 p 是什麼。
s 一看就知道是sequence（定義的 seq 字串變數是乙個明確的提醒）
回憶一下字串方面的演算法：KMP、AC 自動機、Trie、Manacher。
繼續深入挖掘，可以想到 Manacher 演算法是關於回文串（Palindrome）的，那麼 p 所代表的單詞也顯而易見了。
於是，lps 函式即為Longest Palindrome Sequence，最長回文子串行。
接下來從輸入樣例手算即可。
2樓：rsa
有些遞迴題可以用記憶化的技巧。
即，當遞迴程式不改變全域性變數/指標/引用/靜態變數等時，遞迴函式返回值只和引數有關。
呼叫一次以後，你就把引數對應的返回值記下來，下次呼叫相同的引數就可以直接用，不用再模擬一遍。
lps這個題，引數只有i和j，可以畫一張二維的表，每個格仔代表一種可能的引數(i,j)，然後按順序填表就行了。
3樓：yanQval
一般的閱讀程式寫結果都是一些經典的演算法的實現，只要見過的比較多，好多都能一眼看出來這個是幹嘛的。如果不能一眼看出來，就分析分析變數名，分析分析語義，也能看出來他在幹什麼，不過這個也需要一些經驗吧，比如你對設計動態規劃的轉移特別熟悉的話，上面那個是能很明顯看出來的。
如果實在看不出來的，一般都是一些較好模擬的，用一張大點的紙就行了，注意記好傳入的值和傳出的
4樓：
謝不邀。
這個題應該是去年提高組看程式寫結果第三題，當時考場上包括我周圍大部分人都一眼秒了。
看到這種遞迴上來就直接模擬不是很明智，最後可能都沒時間檢查，而且原題字串比較短，如果稍微長一點也是要占用一點時間的，所以碰到遞迴的問題無論是普及組還是提高組最好還是弄清楚遞迴的含義。
比如這個題看到lps，看到乙個字串，看到i，j兩個變數模擬指標，而且i遞增j遞減，就應該能猜到這個是想在字串頭尾找什麼東西，再看到s[i]==s[j]就能反應過來這個可能是在找字串最長回文子串行了。不放心還能再驗證一下，頭尾指標相同的答案明顯是1，頭指標超過了尾指標答案明顯是0，如果當前頭指標指的字母和尾指標指的字母相等就順著移一下，不然一定有乙個字母取不了，就移其中乙個然後取個max。所有題目做完如果還有時間就再人工模擬遞迴過程是最好的（一般來說初賽題目做完都能剩下一半時間
初賽裡面大部分的遞迴都是有意義的，沒有意義的毒瘤模擬題我也遇到過，這種就只能畫個棧了
5樓：Shawn Zhou
遞迴題還是腦容量大好做一些，要不腦子裡存不下那麼多變數，遞迴就會暈。
其實對於題主所給的去年那道題 @OFShare 同學的答案已經解釋的很詳細了，我想就模擬遞迴這個問題說一下我個人的做法，可能不適用於所有人，大家謹慎選用。
每次return的東西不一樣的問題。程式返回的值是啥就是啥，比如說邊界條件返回0或者1。而如果返回的是乙個遞迴式，比如說lps(seq,i+1,j-1) + 2，那就按照這個函式計算的規則繼續算lps(seq,i+1,j-1) 就好，直到算出來沒有其他式子，此可謂「遞」。
我們在每一層都算出了相應的值，按照規則，應該把值返回到上一層（可以借助在草稿紙上畫圖來感性的認知一下這個過程，如果你對遞迴的過程不了解），一層一層返回，一直返回到第一層就是答案了。此之曰「歸」。
說的具體一點，拿到乙個遞迴題，仍然是要保持清醒，在腦內模擬這個過程，利用好草稿紙，把每一層的中間變數都記錄一下，換句話說，就是模擬系統棧了。這樣做應該是沒有問題的。
沒法講得很具體，因為有很多技巧只能說是「只可意會不可言傳」，沒法用準確的語言去表述，想要掌握還是得需要不斷的摸索和練習才行2333
嗯差不多就是這些了
6樓：
我沒有搞過noip，這裡只能說下我對遞迴這類題的做法(ps:因為曾經的我也看不懂這類遞迴題，更是不會寫遞迴的題，所以深有同感。。。我覺得新手程式設計的最大攔路虎就是遞迴了，後面的dfs回溯記憶化搜尋等各種搜尋都是遞迴的直接體現，我個人認為遞迴理解的清楚，碼力會有極大提高，當然這是後話了)
我理解這類題，是以"狀態"入手的（個人認為"狀態「這個詞，它是理解很多概念和演算法的關鍵）
上面就是我模擬這個遞迴程式寫的程式。
這裡的（0,10）就是乙個狀態(seq在所有狀態都是不變的，所以省略了)
還有左邊部分的(1,9)算出來是5，所以右邊部分的(1,9)就直接知道也是5了(這就是記憶化搜尋，記住某個狀態的值，當再算這個狀態時，直接返回，當然你給的程式這部分沒寫)
最後說一下如何寫遞迴程式(個人感覺就是找到」狀態「，遞迴邊界，和狀態如何轉移，這聽起來好像動態規劃DP呀***就是這麼回事)，你給的程式就是標準的遞迴寫法，一般先寫轉移部分，最後寫邊界，邊界寫在前面。
大概5-10分鐘可以做完(不知道你們noip考多久)
題主加油，多看書，多刷題b(￣▽￣)d
7樓：cdcq
如果真的想不清楚的話，不妨嘗試在紙上模擬
現在進行到了第幾層，這一層的幾個變數都是什麼返回之後按照在紙上的記錄回到上一層處理
這其實就是在紙上仿照計算機執行遞迴程式吧
人腦模擬不能的話可能是大腦記憶體不夠導致爆棧（就是腦中不能同時裝太多變數233
NOIP初賽應該如何準備？
Hawkii 其實就是找題刷題啊，洛谷上有整理。試題列表 洛谷有題 或者買一本資訊學奧賽一本通初賽篇 c 自己學。此外，我還自製了乙個小程式可以方便在手機上刷初賽的選擇題，可以支援一下。 洛蕭琳 去年考砸了，本來以為可以考80多分的，但是只考了60分，當時我以為自己肯定GG了，連初賽都過不了，急了我...
如何評價noip2018初賽？
座標浙江，教練說估分低於80就可以補文化課了 於是我就去補文化課了 抱歉抱歉生而為浙江人我很抱歉 天台見吧 浙江這種弱省太毒瘤了Orz 我是誰蘑菇貓 選擇題賊幾把簡單，我十五題就錯了兩道 程式填空賊幾把難，錯了將近一半 不過反正我是上海的，這次還考得那麼難，估計三十分都能進複賽，74分肯定沒問題了 ...
如何看待NOIP2016初賽疑似洩題？
Shawn Zhou CCF需要對此做出合理的解釋和處理。照今年這情況，如果我明年得到了初賽題，我把原題題設改的面目全非而題目要求基本相同 打 擦邊球 然後冠之以名為某校第x次NOIP模擬題在網上發帖求助，初賽完仍然有許多人向CCF舉報我，拿到了同樣的結果。豈不滑天下之大稽？ 講道理CCF這處理方式...