public static int numDecodings_dp(String s) {

    int[] dp = new int[s.length() + 1];
    dp[s.length()] = 1;

    for (int i = s.length() - 1 ; i >= 0 ; i--) {

      if (s.charAt(i) == '0') {
        dp[i] = 0;
      } else {
        dp[i] = dp[i + 1];

        if (i + 2 <= s.length() && (s.charAt(i) == '1' || (s.charAt(i) == '2' && s.charAt(i + 1) < '7'))) {
          dp[i] += dp[i + 2];
        }
      }

    }

    System.out.println(Arrays.toString(dp));
    return dp[0];
  }