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

Idea

典型的DP题
考虑字符串”21212”
从末尾考虑 它的解码种数为”2121” +”2”的解码数 或者”212”+”12”的解码数
又因为在”2121”+”2”中 , 2 1 2 1 2这一种情况已经被包含 ,所以”12”的解码数只剩下一种.
也就是 “21212”的解码种数 =”2121” 的解码种数 +”212”的解码种数

由此 我们可以很自然地考虑DP来解决这个问题

Code

  1.   public static int numDecodings(String s) {
  2.         int size=s.length();
  3.         Boolean tag=false;
  4.         if(s.charAt(0)=='0')
  5.             return 0;
  6.         for(int i=0;i<size-1;i++)
  7.         {
  8.             if(s.charAt(i)=='0'&&s.charAt(i+1)=='0')
  9.                 tag=true;
  10.         }
  11.         if(tag)
  12.             return 0;
  13.         if(size==1 )
  14.             return 1;
  15.         int[] dp=new int[size+1];
  16.         dp[0]=1;
  17.         dp[1]=1;
  18.         char end;
  19.         for(int i=1;i<size;i++) {
  20.             end = s.charAt(i);
  21.             if(end=='0' )
  22.             {
  23.                 int c=s.charAt(i-1)-'0';
  24.                 if(c>2)
  25.                 {
  26.                     dp[i+1]=0;
  27.                 }
  28.                 else
  29.                    dp[i+1]=dp[i-1];
  30.             }
  31.             else {
  32.                 int a = s.charAt(i - 1) - '0';
  33.                 int b = s.charAt(i) - '0';
  34.                 if (a * 10 + b <= 26 && a!=0) {
  35.                     dp[i + 1] = dp[i] + dp[i - 1];
  36.                 } else {
  37.                     dp[i + 1] = dp[i];
  38.                 }
  39.             }
  40.         }
  41.         return dp[size];
  42.     }