leetcode: decode ways dp 解法

Question

leetcode: 解码方式

我尝试使用 dp 来优化我的递归，但是似乎效果不佳，因为运行时间已超过限制。任何人都可以帮我处理代码并告诉我 dp 出了什么问题吗？

class Solution {
public:
    int numDecodings(string s) {
        
        int totalnum;
        *map<string, int> dp;*
        stringstream ss;
        int sint;
        string s11=s.substr(0,2);
        stringstream geek(s11);
        geek>>sint;
        if(dp[s]){
            totalnum=dp[s];
        }
        else if(s[0]=='0'){
            return 0;
        }else if(sint>26){
            string s1=s.substr(1,s.length()-1);
            totalnum=numDecodings(s1);
        }
        else
        {
        if(s.length()==1){
            return 1;
        }
        else if(s.length()==2){
            string s1=s.substr(1,s.length()-1);
            if(s[s.length()-1] !=0){totalnum=numDecodings(s1)+1;}
            else{totalnum=numDecodings(s1);}
        }
        else if(s.length()>2){
            string s1=s.substr(1,s.length()-1);
            string s2=s.substr(2,s.length()-2);
            totalnum=numDecodings(s1)+numDecodings(s2);}
        }
        
        *dp.insert(pair<string, int>(s, totalnum));*
        return totalnum;
    }
};

Answer 1

索引可以有两种状态：作为第一个数字或第二个数字。尽量避免在解决方案中创建更多字符串。

class Solution:
    def numDecodings(self, s: str) -> int:
      if s[0] == '0':
        return 0

      dp = [[0, 0] for i in range(len(s) + 1)]

      dp[0][0] = 1
      dp[1][0] = 1

      for i in range(1, len(s)):
        # zero must be second
        if s[i] == '0':
          if s[i-1] not in ['1', '2']:
            return 0
          dp[i+1] = [0, dp[i][0]]
  
        elif '00' < s[i-1:i+1] < '27' and s[i-1] != '0':
          dp[i+1] = [sum(dp[i]), sum(dp[i-1])]
    
        else:
          dp[i+1] = [sum(dp[i]), 0]
    
      return sum(dp[len(s)])

leetcode: decode ways dp 解法

leetcode: decode ways dp solution

decode

dynamic-programming