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）
著作權歸作者所有仪搔。商業(yè)轉載請聯(lián)系作者獲得授權跳纳，非商業(yè)轉載請注明出處趴腋。
）
解析
遞歸和動態(tài)規(guī)劃兩種解法。本題解講述如何從遞推轉換成動態(tài)規(guī)劃山害。
從后往前遍歷。如果
以22067為例凌箕，從后往前遍歷枪萄。
首先如果為7。很顯然是1種7->G
如果為67史飞。很顯然還是1種67->FG
如果為067尖昏。結果為0。
如果為2067构资。 結果為numDecodings（20 67）+ numDecodings（2 067）= numDecodings（20 67）->TFG
如果為22067抽诉。 結果為numDecodings（2 2067）+ numDecodings（22 067）= numDecodings（2 2067）->BTFG
從中，我們可以看出規(guī)律吐绵。
如果開始的數(shù)為0迹淌，結果為0河绽。
如果開始的數(shù)加上第二個數(shù)小于等于26。結果為 numDecodings（start+1）+ numDecodings（start +2）
如果開始的數(shù)加上第二個數(shù)大于26巍沙。結果為 numDecodings（start +1）
public int numDecodings(String s) {
? ? ? ? if (s == null || s.length() == 0) {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? return digui(s, 0);
? ? }
//遞歸的套路葵姥，加一個index控制遞歸的層次
? ? private int digui(String s, int start) {
? ? ? ? //遞歸的第一步，應該是加終止條件句携，避免死循環(huán)榔幸。
? ? ? ? if (s.length() == start) {
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? //以0位開始的數(shù)是不存在的
? ? ? ? if (s.charAt(start) == '0') {
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? //遞歸的遞推式應該是如果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;
? ? }
遞歸解法存在大量的重復計算從中可以看出矮嫉，在計算中進行了大量的重復計算削咆，因此〈浪瘢可以想辦法將重疊子問題記錄下來拨齐，避免重復計算。
引入一個數(shù)組dp[]昨寞，用來記錄以某個字符為開始的解碼數(shù)瞻惋。動態(tài)規(guī)劃其實就是一個填表的過程。整個過程的目標就是要填好新增的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];
? ? }
