leetcode——091
（
作者：reedfan
鏈接：https://leetcode-cn.com/problems/decode-ways/solution/java-di-gui-dong-tai-gui-hua-kong-jian-ya-suo-by-r/
來源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
）
解析
遞歸和動(dòng)態(tài)規(guī)劃兩種解法。本題解講述如何從遞推轉(zhuǎn)換成動(dòng)態(tài)規(guī)劃。
從后往前遍歷。如果
以22067為例，從后往前遍歷。
首先如果為7。很顯然是1種7->G
如果為67。很顯然還是1種67->FG
如果為067。結(jié)果為0。
如果為2067。 結(jié)果為numDecodings（20 67）+ numDecodings（2 067）= numDecodings（20 67）->TFG
如果為22067。 結(jié)果為numDecodings（2 2067）+ numDecodings（22 067）= numDecodings（2 2067）->BTFG
從中，我們可以看出規(guī)律。
如果開始的數(shù)為0，結(jié)果為0。
如果開始的數(shù)加上第二個(gè)數(shù)小于等于26。結(jié)果為 numDecodings（start+1）+ numDecodings（start +2）
如果開始的數(shù)加上第二個(gè)數(shù)大于26。結(jié)果為 numDecodings（start +1）
public int numDecodings(String s) {
? ? ? ? if (s == null || s.length() == 0) {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? return digui(s, 0);
? ? }
//遞歸的套路，加一個(gè)index控制遞歸的層次
? ? private int digui(String s, int start) {
? ? ? ? //遞歸的第一步，應(yīng)該是加終止條件，避免死循環(huán)。
? ? ? ? if (s.length() == start) {
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? //以0位開始的數(shù)是不存在的
? ? ? ? if (s.charAt(start) == '0') {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? //遞歸的遞推式應(yīng)該是如果index的后兩位小于等于26，?
? ? ? ? // digui(s, start) = digui(s, start+1)+digui(s, start+2)?
? ? ? ? // 否則digui(s, start) = digui(s, start+1)
? ? ? ? int ans1 = digui(s, start + 1);
? ? ? ? int ans2 = 0;
? ? ? ? if (start < s.length() - 1) {
? ? ? ? ? ? int ten = (s.charAt(start) - '0') * 10;
? ? ? ? ? ? int one = (s.charAt(start + 1) - '0');
? ? ? ? ? ? if (ten + one <= 26) {
? ? ? ? ? ? ? ? ans2 = digui(s, start + 2);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return ans1 + ans2;
? ? }
遞歸解法存在大量的重復(fù)計(jì)算從中可以看出，在計(jì)算中進(jìn)行了大量的重復(fù)計(jì)算，因此?？梢韵朕k法將重疊子問題記錄下來，避免重復(fù)計(jì)算。
引入一個(gè)數(shù)組dp[]，用來記錄以某個(gè)字符為開始的解碼數(shù)。動(dòng)態(tài)規(guī)劃其實(shí)就是一個(gè)填表的過程。整個(gè)過程的目標(biāo)就是要填好新增的dp[]數(shù)組。
public int numDecodings(String s) {
? ? ? ? if (s == null || s.length() == 0) {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? int len = s.length();
? ? ? ? int[] dp = new int[len + 1];
? ? ? ? dp[len] = 1;
? ? ? ? if (s.charAt(len - 1) == '0') {
? ? ? ? ? ? dp[len - 1] = 0;
? ? ? ? } else {
? ? ? ? ? ? dp[len - 1] = 1;
? ? ? ? }
? ? ? ? for (int i = len - 2; i >= 0; i--) {
? ? ? ? ? ? if (s.charAt(i) == '0') {
? ? ? ? ? ? ? ? dp[i] = 0;
? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? }
? ? ? ? ? ? if ((s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0') <= 26) {
? ? ? ? ? ? ? ? dp[i] = dp[i + 1] + dp[i + 2];
? ? ? ? ? ? } else {
? ? ? ? ? ? ? ? dp[i] = dp[i + 1];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[0];
? ? }
