前言：之前我不是說，我后續可能會講一下遞歸嗎，現在它來了，這道題會用到回溯的方法，并且比較純粹哦

解題思路：

? ? ? ? 1.獲取信息：（下面這些信息差不多是力扣上面的題目信息了，所以我這一環節在這次題解中的意義不大）

? ? ? ? ? ? ? ? 外觀數列是一個數位字符串序列，由遞歸公式定義：

• countAndSay(1) = "1"
• countAndSay(n)?是?countAndSay(n-1)?的行程長度編碼。

? ? ? ? ? ? ? ? 行程長度編碼（RLE）是一種字符串壓縮方法，其工作原理是通過將連續相同字符（重復兩次或更多次）替換為字符重復次數（運行長度）和字符的串聯。例如，要壓縮字符串?"3322251"?，我們將?"33"?用?"23"?替換，將?"222"?用?"32"?替換，將?"5"?用?"15"?替換并將?"1"?用?"11"?替換。因此壓縮后字符串變為?"23321511"。

? ? ? ? ? ? ? ? 要求給定一個整數n，返回外觀數列的第n個元素，即返回遞歸公式代入n后的值

? ? ? ? 2.分析題目：

? ? ? ? ? ? ? ? 它給出了遞歸公式，就是提醒你，可以使用遞歸來解決這道題

? ? ? ? ? ? ? ? 并且說明了行程長度編碼壓縮字符串的原理，更方便你理解了嘛

? ? ? ? ? ? ? ? 現在來講一下遞歸：（你可以結合我下面代碼來進行理解）

? ? ? ? ? ? ? ? 我們都知道，那些使用遞歸的題中，一般一個函數里面是嵌套著一個相同的函數對吧

? ? ? ? ? ? ? ? 例如 Find()函數里面套一個Find()函數

? ? ? ? ? ? ? ? 這就是遞歸的關鍵之一，你可以理解成，里面套著的那個函數是開啟外面這個函數的“鑰匙”

? ? ? ? ? ? ? ? 現在，外面里面有了一個嵌套的函數對吧，那么在代碼執行到那個嵌套的函數時，我們知道，代碼是一段一段執行的，對吧，那么在執行完這個嵌套的函數之前，下面的代碼它是不會執行的對吧，所以在獲取到“鑰匙”之前，下面的代碼是不會進行操作的

? ? ? ? ? ? ? ? 那么，你是不是可以講它看作是一個深入的過程，它在深入到一定程度后，就會結束，即：獲取到“鑰匙”，就會開始執行下面的代碼，即開始執行外部函數

? ? ? ? ? ? ? ? 那么它深入地程度，你可以來進行規定，比如設置一個條件，滿足這個條件就返回，就可以返回較淺的層面

? ? ? ? ? ? ? ? 這樣的話，就有了很多鉆空子的操作，我舉一個現實的例子來抽象地說一下吧

? ? ? ? ? ? ? ? 比如一個車間需要加工一把椅子，老板給你說，讓你安排一下，做好了就把自己白富美的女兒嫁給你，讓你走上人生巔峰

? ? ? ? ? ? ? ? 你現在要做一把椅子，你知道需要椅子的腿，椅子的靠背，椅子的墊子來組成椅子

? ? ? ? ? ? ? ? 你沒有這些東西，你就算知道怎么把它們組合起來，也不能操作，因為巧婦難為無米之炊（這就是我說的，缺少“鑰匙”，你不能進行外部函數下面的代碼操作）

? ? ? ? ? ? ? ? 這個時候就需要這些東西對吧，那你就需要再加一個更深層次的步驟，將自己的需求傳遞給這個更深層次的部門

? ? ? ? ? ? ? ? 這個更深層次的部門的操作就是將木材加工成上述東西，但是又沒有木材，也不能開啟它們的操作

? ? ? ? ? ? ? ? 需要木材，我們知道，木材就是這次加工的最底線了，對吧，這個底線是人為規定的，意思就是我們希望它是底線，那就是底線，這里就是我說的，深入到一定程度時，需要一個條件來阻止它繼續深入，你可以理解成，這個工廠才是你考慮得范圍，至于木材怎么來的，你不用管，你只用管你該管的范圍，即：題目要求的范圍

? ? ? ? ? ? ? ? 現在我們取得了木材，那么就返回到了較淺的步驟，就是加工木材的步驟，工人獲取了木材，即：“鑰匙”，那就可以進行后續操作了，它們進行后續操作了之后，就返回他們加工的東西

? ? ? ? ? ? ? ? 我現在獲得了組合椅子需要的東西，現在我就可以進行我下面的操作了，我完成了之后，就是結果了，可以交給老板驗貨

? ? ? ? ? ? ? ? 迎娶白富美，走上人生巔峰，畢竟，人人都想成為達叔，軟飯硬吃

? ? ? ? 3.示例查驗：?

? ? ? ? ? ? ? ? 你可以結合示例，來品味一下遞歸，（上面說的，其實比較偏向回溯，但遞歸的核心思想還是不會變的）

? ? ? ? 4.嘗試編寫代碼：

? ? ? ? ? ? ? ? （1）回溯法

? ? ? ? ? ? ? ? ? ? ? ? 思路就不過多闡述了，這道題比較純粹，就直接上代碼了

class Solution {
public:string countAndSay(int n) {if(n==1)return "1";string str=countAndSay(n-1),res;int num=1,size=str.size();for(int i=1;i<=size;i++){if(i==size){res+=(num+'0');res+=str[i-1];break;}if(str[i]==str[i-1])num++;else{res+=(num+'0');res+=str[i-1];num=1;}}return res;}
};

? ? ? ? ? ? ? ? （2）打表嘛

? ? ? ? ? ? ? ? ? ? ? ? 思路：給出了n的范圍是1到30，那你直接把1到30每個數得到的結果列舉出來，輸入n后，直接返回對應結果就可以了，這里就不寫代碼了，太麻煩了