DP

package com.gokul.demo.InProgress.DP;
import java.util.Arrays;
public class DynamicProbs {
public static void main(String[] args) {
System.out.println(numDecodings("2101"));
}
public static int numDecodings(String s) {
int[] arr = new int[s.length()];
Arrays.fill(arr, -1);
return countOfDecodings(s, 0, arr);
}
private static int countOfDecodings(String s, int i, int[] arr) {
if (i == s.length()) {
return 1;
}
if (arr[i] != -1) {
return arr[i];
}
arr[i] = 0;
if (isValid(s.charAt(i) - '0', 1)) {
arr[i] += countOfDecodings(s, i + 1, arr);
}
if (i > 0 && isValid((s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0', 2)) {
arr[i] += countOfDecodings(s, i + 2, arr);
}
return arr[i];
}
private static boolean isValid(int c, int l) {
if (l == 1) {
return c >= 1 && c <= 9;
}
return c >= 10 && c <= 26;
}
}