My c++ dp solution


  • 0
    D

    I got dp[i] from end to begin.

    int numDecodings(string s) {
    if (s.length() > 0){
        int dp[s.length()+1];
        dp[s.length()] = 1;
        for (long long i=s.length()-1; i>=0; i--) {
            if (i == s.length() -1){
                if (s[i] == '0')
                    dp[i] = 0;
                else
                    dp[i] = 1;
            }
            else{
                dp[i] = 0;
                if (s[i] != '0'){
                    dp[i] += dp[i+1];
                    if (s[i]<='1' || (s[i]=='2' && s[i+1]<='6'))
                        dp[i] += dp[i+2];
                }
            }
        }
        
        return dp[0];
    }
    else
        return 0; 
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.