/**
 * Name: Decode Ways
 * Number: 91
 * Tag: DP/String
 * Main Point: p[i] represent the number of ways to decode s.substring(0, j); 
   two cases: 
   if s(i) != 0, then s(i) can be decoded just by this digit alone
   // if s(i-1, i) is between (10, 26), then s(i) can be decoded together with the digit before it
 * Time Complexity: O(s.length());
 * Space Complexity: O(s.length());
**/
class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        //def: dp[i] represent the number of ways to decode s.substring(0, j);
        int len = s.length();
        int[] dp = new int[len + 1];
        //initialize
        dp[0] = 1;
        dp[1] = s.charAt(0) != '0' ? 1 : 0;
        //formula
        for (int i = 2; i <= len; i++) {       
            //if s(i) != 0, then s(i) can be decoded just by this digit alone
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            } 
            // if s(i-1, i) is between (10, 26), then s(i) can be decoded together with the digit before it 
            int two_digits = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two_digits >= 10 && two_digits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[len];
    }
}
@@ -1301,8 +1301,1244 @@
 %0A    %7D%0A%7D
+%0A%0A/**%0A * Improvement: dp%5Bi%5D only relies on dp%5Bi - 1%5D and dp%5Bi - 2%5D,%0A   so we just need two variables to record dp%5Bi - 1%5D and dp%5Bi - 2%5D%0A * Time Complexity: O(s.length)%0A * Space Complexity: O(1)%0A**/%0Aclass Solution %7B%0A    public int numDecodings(String s) %7B%0A        if (s == null %7C%7C s.length() == 0) return 0;%0A        //def: dp%5Bi%5D represent the number of ways to decode s.substring(0, j);%0A        int len = s.length();%0A        //int%5B%5D dp = new int%5Blen + 1%5D;%0A        //initialize%0A        int dp_llast = 1;%0A        int dp_last = s.charAt(0) != '0' ? 1 : 0;%0A        int dp_now = dp_last;%0A        //formula%0A        for (int i = 2; i %3C= len; i++) %7B %0A            dp_now = 0;%0A            //if s(i) != 0, then s(i) can be decoded just by this digit alone%0A            if (s.charAt(i - 1) != '0') %7B%0A                dp_now = dp_last;%0A            %7D %0A            // if s(i-1, i) is between (10, 26), then s(i) can be decoded together with the digit before it %0A            int two_digits = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');%0A            if (two_digits %3E= 10 && two_digits %3C= 26) %7B%0A                dp_now += dp_llast;%0A            %7D%0A            dp_llast = dp_last;%0A            dp_last = dp_now;%0A        %7D%0A        return dp_now;%0A    %7D%0A%7D

Improve Space Complexity of DP