題目

https://leetcode.com/problems/decode-ways/

題解

dp 問題，首先用模擬的辦法試一下，理清楚狀態轉移關系。

當走到 i 位置時，i 有兩種選擇：

• i 不與 i-1 組合，此時，只要 i 位置不是 0，總的組合方式等于前一個狀態的所有組合方式
• i 與 i-1 組合，此時，只要前一個狀態是非組合，且組合之后小于等于 26，則總的組合方式等于前一個非組合的方式數量

看草稿：

class Solution {public int numDecodings(String s) {int L = s.length();int[][] dp = new int[L][2]; // dp[不組合的有效數量][與i-1組合的有效數量]dp[0][0] = s.charAt(0) == '0' ? 0 : 1;// dp[0][1] = 0;for (int i = 1; i < L; i++) {int n1 = s.charAt(i - 1) - '0';int n2 = s.charAt(i) - '0';if (n2 != 0) { // i非0，才能不組合dp[i][0] = dp[i - 1][0] + dp[i - 1][1];}if (n1 != 0 && 10 * n1 + n2 <= 26) { // i-1非0，i可嘗試和i-1組合dp[i][1] = dp[i - 1][0];}}return dp[L - 1][0] + dp[L - 1][1];} }

總結

以上是生活随笔為你收集整理的leetcode 91. Decode Ways | 91. 解码方法（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。