動態規劃：91. 解碼方法

動態規劃：單個數組或者字串要用動態規劃時，可以把動態規劃

dp［i］ 定義為 nums［0：i］ 中想要求的結果

；當兩個陣列或者字串要用動態規劃時，可以把動態規劃定義成兩維的

dp［i］［j］ ，其含義是在 A［0：i］ 與 B［0：j］ 之間匹配得到的想要的結果

。

這題把dp［i］看出，0-i 區間有多少種解碼方式：

參考派樓梯：

如果

沒有條件限制

的話，這題解法和

爬樓梯

完全一樣，

dp［i］=dp［i-1］+dp［i-2］

這裡在for 迴圈裡面加上兩種條件

當前item 不等於為0 ；

dp［i］ += dp［i-1］；

/前面一個數字是1， 或者前面數字是2，當前數字小於7

dp［i］ += dp［i-2］；

class Solution91 { public int numDecodings（String s） { if（s。length（） == 0）{ return 0； } int［］ dp = new int［s。length（）］； if（s。charAt（0） == ‘0’）{ return 0； } dp［0］ = 1； for（int i = 1； i < s。length（）； i++）{ if（s。charAt（i） ！= ‘0’）{ dp［i］ += dp［i-1］； } //前面一個數字是1， 或者前面數字是2，當前數字小於7 if（s。charAt（i-1） == ‘1’ || （s。charAt（i-1） == ‘2’ && s。charAt（i） <= ‘6’））{ if（i-2>=0）{ dp［i］ += dp［i-2］； }else{ dp［i］++；//i-2 < 0 加上一種 } } } return dp［s。length（）-1］； }}

加油：P