91.Decode Ways---dp

题目链接：https://leetcode.com/problems/decode-ways/description/

题目大意：将给出的字符串解码，问有多少种解码方式。解码按照“ABC...Z"->1,2,3...26进行。比如”12“有两种解码方式：1 2（A B），12（L）。

法一（借鉴）：dp。是裴波那挈数列的变形题，根本dp还是裴波那挈数列：dp[i] = dp[i - 1] + dp[i - 2]。从前往后。代码如下（耗时2ms）：

 1     //dp[i]表示从0到i的字符串的解码方式的种类
 2     public int numDecodings(String s) {
 3         if(s.length() == 0) {
 4             return 0;
 5         }
 6         int dp[] = new int[s.length() + 1];
 7         //初始化0
 8         dp[0] = 1;
 9         //计算dp
10         for(int i = 1; i < dp.length; i++) {
11             dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
12             if(i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
13                 dp[i] += dp[i - 2];
14             }
15         }
16         return dp[s.length()];
17     }

View Code

91.Decode Ways---dp

推荐阅读