dp[i][j] - можно ли получить остаток j если длина равна i.
я получал всякие превышение памяти и времени, только потому что я сохранял предка. Но если не сохранять предка, а вычислять самому, то решение будет < 100 миллисекунд. Восстанавливал и находил минимальный ответ через рекурсию  почти как дфс.