前言：最近在刷動(dòng)態(tài)規(guī)劃的算法題目，感覺這一類題目還是有一點(diǎn)難度的，但是不放棄也還是能學(xué)好的，今天給大家分享的是?？途W(wǎng)中的編程題目[把數(shù)字翻譯成字符串]，這是一道經(jīng)典的面試題目，快手，字節(jié)跳動(dòng)等大廠出國這道題目。題目有點(diǎn)繞，需要進(jìn)行分類討論最好配合畫圖工具進(jìn)行理解，這樣能更好理解這道題目。

一.題目

二.進(jìn)一步剖析題目

1.關(guān)于動(dòng)態(tài)規(guī)劃思想

動(dòng)態(tài)規(guī)劃算法的基本思想是：將待求解的問題分解成若干個(gè)相互聯(lián)系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時(shí)候?qū)λM(jìn)行求解，并把答案保存起來，讓以后再次遇到時(shí)直接引用答案，不必重新求解。動(dòng)態(tài)規(guī)劃算法將問題的解決方案視為一系列決策的結(jié)果。

2.分析題目

①分析題目：能夠譯碼的數(shù)字不會(huì)大于26，即有效的譯碼范圍為 [1,26]。

②確定狀態(tài)：以數(shù)組 "12345" 為例，首先要明確兩點(diǎn)：

• 依題意可知，數(shù)組中所有的數(shù)字都必須參與譯碼，比如數(shù)組 "1234" 的某一種譯碼方式為 “1,2,3,4"，那么當(dāng)數(shù)組尾再添加一個(gè)元素 "5" 時(shí)，剛才的譯碼方式就會(huì)變?yōu)?"1,2,3,4,5"，即 "1,2,3,4" 和 "1,2,3,4,5" 是同一種譯碼方式。

由于所有數(shù)字都要參與譯碼，所以只要譯碼方式中存在個(gè)位數(shù) "0"，那么就都是無效的。

• 當(dāng)新加入一個(gè)數(shù)字"5" 時(shí)，其除了可以單獨(dú)作為一個(gè)數(shù)字參與譯碼外，也可以與其左邊的數(shù)字組成數(shù)字組合后再參與譯碼，即 "45" ，然后此時(shí)有多少種譯碼方式就取決于剩余的數(shù)字 即 "123" 了，這和前面所說的是同一個(gè)道理，只是此時(shí)把 "4"和"5" 看作是一個(gè)整體，可以理解為：原本數(shù)組 "123" 存在某種譯碼方式為 "1,2,3"，現(xiàn)在加入 "45"，譯碼方式就變成了 "1,2,3,45"。

由于有效的譯碼范圍為 [1,26]，所以新加入的數(shù)字 "5" 只需要考慮與其左邊的數(shù)字組成兩位數(shù)組合，無需再考慮組成更大的組合了，比如三位數(shù) "345" 等等。

數(shù)字組合必須是十位數(shù)，比如 "0"和"2" 組成的 "02" 也是不符合譯碼要求的。

理解了上面兩點(diǎn)后，現(xiàn)在我們從數(shù)組 "12345" 的子串"1"開始分析，然后逐步往后添加元素，設(shè)數(shù)組 x 有 f(x) 種有效的譯碼方式：

• 當(dāng)數(shù)組為 "1" 時(shí)，有以下譯碼方式：

①1

f("1")=1

• 接著加入數(shù)字"2"，數(shù)組為 "12" 時(shí)，有以下譯碼方式：

①1，2

②12

f("12")=2

其中第①種是從 數(shù)組 "1" 的譯碼方式 演變過來的，就是在其基礎(chǔ)上再加上單個(gè)數(shù)字 "2"。

• 接著加入數(shù)字"3"，數(shù)組為 "123" 時(shí)，有以下譯碼方式：

①1，2，3

②12，3

③1，23

f("123")=3

其中第①、②種是從 數(shù)組 "12" 的譯碼方式 演變過來的，就是在其基礎(chǔ)上再加上單個(gè)數(shù)字 "3"；

而第③種是從 數(shù)組 "1" 的譯碼方式 演變過來的，就是在其基礎(chǔ)上再加上數(shù)字組合 "23"。

• 接著加入數(shù)字"4"，數(shù)組為 "1234" 時(shí)，有以下譯碼方式：

①1，2，3，4
②12，3，4
③1，23，4
④1，2，34
⑤12，34

其中第①、②、③種是從 數(shù)組 "123" 的譯碼方式 演變過來的，就是在其基礎(chǔ)上再加上單個(gè)數(shù)字 "4"；

而第④、⑤種是從 數(shù)組 "12" 的譯碼方式 演變過來的，就是在其基礎(chǔ)上再加上數(shù)字組合 "34"；

由于 "45" 不在有效譯碼的范圍內(nèi)，所以這兩種譯碼方式會(huì)被拋棄掉。

f("1234")=3

可見，數(shù)組 "1234" 的譯碼方式 是由 數(shù)組 "123"的譯碼方式 和 數(shù)組 "12"的譯碼方式 組成的。

• 根據(jù)上面的分析，當(dāng)數(shù)組繼續(xù)擴(kuò)張到 "12345" 時(shí)，那么其譯碼方式就為：

當(dāng)新加入的數(shù)字 "5" 單獨(dú)作為個(gè)位數(shù)參與譯碼時(shí)，此時(shí)的譯碼方式 就等同于 數(shù)組 "1234" 的譯碼方式，這組譯碼方式是有效的，因?yàn)閭€(gè)位數(shù) "5" 在有效的譯碼范圍內(nèi)；

而 "5" 與其前一位數(shù)字組成十位數(shù) "45" 時(shí)，此時(shí)的譯碼方式 就等同于 數(shù)組 "123" 的譯碼方式，而這組譯碼是否有效則取決于 "45" 是否在有效的譯碼范圍內(nèi)。

即 f("12345") = f("12345" - "5") + f("12345" - "45") = f("1234") + f("123") = 3+3 = 6，但是由于 "45" 不在有效的譯碼范圍內(nèi)，所以 f("123") 的結(jié)果不能算在內(nèi)，所以最終結(jié)果應(yīng)該為3。

• 可見，枚舉到某位數(shù)字時(shí)，此時(shí)有多少種譯碼方式，可以由之前的譯碼方式相加得出，即當(dāng)前的狀態(tài)可以利用之前的狀態(tài)，這是典型的動(dòng)態(tài)規(guī)劃。

③狀態(tài)轉(zhuǎn)移方程：f(x)=f(x-1)+f(x-2)（其中 x 表示數(shù)組長度，f(x) 表示有多少種有效的譯碼方式；是否加上 f(x-1) 取決于 nums[x] 是否在 [1,9] 內(nèi)，即 nums[x] 需要滿足不為0；是否加上 f(x-2) 則取決于 nums[i-1] 與 nums[i] 的數(shù)字組合是否在 [10,26] 內(nèi)）

時(shí)間復(fù)雜度：O(N) ，需要遍歷一次數(shù)組

空間復(fù)雜度：O(N) ，需要聲明一個(gè)狀態(tài)數(shù)組記錄f(x)

3.C++代碼

class Solution {public:int solve(string nums) {// write code hereif(nums[0]=='0')return 0;vector<int>dp(nums.size(),0);dp[0]=1;for(int i=1;i<dp.size();i++){if(nums[i]!='0'){if(nums[i-1]=='1'){dp[i]=dp[i-1]+(i-2>=0?dp[i-2]:1);continue;}if(nums[i-1]=='2'&&(nums[i]-'0'>0&&nums[i]-'0'<7)){dp[i]=dp[i-1]+(i-2>=0?dp[i-2]:1);continue;}    dp[i]=dp[i-1];            }else {if(nums[i-1]-'0'==1||nums[i-1]-'0'==2){dp[i]=dp[i-1];continue;}return 0;           }}return dp[nums.size()-1];
}
};