Как можно преобразовать следующую рабочую рекурсию + код мемуализации в решение динамического программирования в формате табуляции? на положительную сторону.
Ссылка на задачу: https://leetcode.com/problems/valid-par ... scription/
public static boolean checkValidStringMem(String s)
{
int n = s.length();
Boolean[][] mem = new Boolean[n][n + 1];
return checkValidStringMem(s, 0, 0, mem);
}
public static boolean checkValidStringMem(String s, int i, int count, Boolean[][] mem)
{
if (count < 0)
return false;
if (i == s.length())
return count == 0;
if (mem[count] != null)
return mem[count];
if (s.charAt(i) == '(')
return mem[count] = checkValidStringMem(s, i + 1, count + 1, mem);
else if (s.charAt(i) == ')')
return mem[count] = checkValidStringMem(s, i + 1, count - 1, mem);
else // '*' can be ')' or '(' or empty character
{
return mem[count] = checkValidStringMem(s, i + 1, count + 1, mem) ||
checkValidStringMem(s, i + 1, count - 1, mem) ||
checkValidStringMem(s, i + 1, count, mem);
}
}
Подробнее здесь: https://stackoverflow.com/questions/794 ... tion-to-dp
