LeetCode 91. Decode Ways

• 2019 年 12 月 16 日
• 筆記

题目

动态规划

class Solution {  public:      int dp[100005];      int numDecodings(string s) {            string str="";            if(s[0]=='0')              return 0;          dp[0]=1;            if(s.length()<=1)              return dp[s.length()-1];              str+=s[0];          str+=s[1];            int x = atoi(str.c_str());          if(x<=26&&x>=1)          {              dp[1]++;          }            if(s[1]!='0')          {                dp[1]++;          }            for(int i=2;i<s.length();i++)          {              str="";              str+=s[i-1];              str+=s[i];                int x = atoi(str.c_str());              if(x<=26&&x>=1&&s[i-1]!='0')              {                  dp[i] += dp[i-2];              }                if(s[i]!='0')                  dp[i] += dp[i-1];          }              return dp[s.length()-1];        }  };